There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

Weiterer Publikationstyp


Details zur Publikation

Autor(en): Kleinert T, Schmidt M, Plein F, Labbé M
Jahr der Veröffentlichung: 2019
Sprache: Englisch


Abstract

One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem is as hard as solving the original bilevel problem.


FAU-Autoren / FAU-Herausgeber

Kleinert, Thomas
Juniorprofessur für Optimierung von Energiesystemen
Schmidt, Martin Prof. Dr.
Juniorprofessur für Optimierung von Energiesystemen


Zitierweisen

APA:
Kleinert, T., Schmidt, M., Plein, F., & Labbé, M. (2019). There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization.

MLA:
Kleinert, Thomas, et al. There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization. 2019.

BibTeX: 

Zuletzt aktualisiert 2019-23-04 um 15:19