Optimization Online


Presolving Linear Bilevel Optimization Problems

Thomas Kleinert (thomas.kleinert***at***fau.de)
Julian Manns (julian.manns***at***fau.de)
Martin Schmidt (martin.schmidt***at***uni-trier.de)
Dieter Weninger (dieter.weninger***at***fau.de)

Abstract: Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization.

Keywords: Linear Bilevel Optimization, Presolve, Computational Analysis

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 03/05/2021
Entry Accepted: 03/05/2021
Entry Last Modified: 07/14/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society