Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

Thomas Kleinert (), Martine Labbé (), Fr¨ank Plein () and Martin Schmidt ()
Additional contact information
Thomas Kleinert: Discrete Optimization, Friedrich-Alexander-Universit¨at Erlangen-Nürnberg, 91058 Erlangen, Germany
Martine Labbé: Department of Computer Science, Université Libre de Bruxelles, 1050 Brussels, Belgium, Inria Lille–Nord Europe, 59650 Villeneuve d’Ascq, France
Fr¨ank Plein: Department of Computer Science, Université Libre de Bruxelles, 1050 Brussels, Belgium, Inria Lille–Nord Europe, 59650 Villeneuve d’Ascq, France
Martin Schmidt: Department of Mathematics, Trier University, 54296 Trier, Germany

Operations Research, 2020, vol. 68, issue 6, 1716-1721

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

Keywords: bilevel optimization; mathematical programs with complementarity constraints (MPCC); bounding polyhedra; big-M; hardness. (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1944 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:6:p:1716-1721

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().