• search hit 2 of 2
Back to Result List

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

  • 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 (for any point in the projection of the high-point relaxation onto the leader's decision space) is as hard as solving the original bilevel problem.

Download full text files

Export metadata

Metadaten
Author:Thomas Kleinert, Martine Labbé, Fränk Plein, Martin Schmidt
Parent Title (German):Operations Research
Document Type:Preprint
Language:English
Date of Publication (online):2019/04/23
Date of first Publication:2019/04/23
Release Date:2019/04/23
Tag:Big-M; Bilevel optimization; Bounding polyhedra; Hardness; Mathematical programs with complementarity constraints (MPCC)
Issue:68(6)
Page Number:6
First Page:1716
Last Page:1721
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