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

Kleinert T, Schmidt M, Plein F, Labbé M (2020)


Publication Language: English

Publication Status: Accepted

Publication Type: Journal article, Original article

Future Publication Type: Journal article

Publication year: 2020

Journal

Book Volume: 68

Pages Range: 1625-1931

Article Number: C2

Journal Issue: 6

URI: https://pubsonline.informs.org/doi/10.1287/opre.2019.1944

DOI: 10.1287/opre.2019.1944

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.

Authors with CRIS profile

Related research project(s)

How to cite

APA:

Kleinert, T., Schmidt, M., Plein, F., & Labbé, M. (2020). There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization. Operations Research, 68(6), 1625-1931. https://dx.doi.org/10.1287/opre.2019.1944

MLA:

Kleinert, Thomas, et al. "There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization." Operations Research 68.6 (2020): 1625-1931.

BibTeX: Download