Technical note-There's no free lunch: On the hardness of choosing a correct big-M in bilevel optimization

Kleinert T, Labbe M, Plein F, Schmidt M (2020)


Publication Type: Journal article

Publication year: 2020

Journal

Book Volume: 68

Pages Range: 1716-1721

Journal Issue: 6

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

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Kleinert, T., Labbe, M., Plein, F., & Schmidt, M. (2020). Technical note-There's no free lunch: On the hardness of choosing a correct big-M in bilevel optimization. Operations Research, 68(6), 1716-1721. https://dx.doi.org/10.1287/OPRE.2019.1944

MLA:

Kleinert, Thomas, et al. "Technical note-There's no free lunch: On the hardness of choosing a correct big-M in bilevel optimization." Operations Research 68.6 (2020): 1716-1721.

BibTeX: Download