• search hit 4 of 84
Back to Result List

Presolving Linear Bilevel Optimization Problems

  • 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.

Download full text files

Export metadata

Metadaten
Author:Thomas Kleinert, Julian Manns, Martin Schmidt, Dieter Weninger
DOI:https://doi.org/10.1016/j.ejco.2021.100020
Parent Title (English):EURO Journal on Computational Optimization
Document Type:Article
Language:English
Date of Publication (online):2021/03/05
Date of first Publication:2021/03/05
Release Date:2021/03/05
Tag:Computational Analysis; Linear Bilevel Optimization; Presolve
Issue:9
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
Universität Trier
Subprojects:A05
Z01
B08
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International