Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/288675 
Erscheinungsjahr: 
2020
Quellenangabe: 
[Journal:] Optimization Letters [ISSN:] 1862-4480 [Volume:] 15 [Issue:] 4 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 1027-1040
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.
Schlagwörter: 
Bilevel optimization
Valid inequalities
Branch-and-cut
Computational analysis
Cxx
JEL: 
C11
C46
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.