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

Thomas Kleinert 1 Martine Labbé 2 Fränk Plein 2 Martin Schmidt 3
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-02106642
Contributor : Fränk Plein <>
Submitted on : Monday, June 17, 2019 - 4:13:24 PM
Last modification on : Tuesday, June 18, 2019 - 1:26:05 AM

File

2019-06-17-preprint-version.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02106642, version 2

Collections

Citation

Thomas Kleinert, Martine Labbé, Fränk Plein, Martin Schmidt. There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization. 2019. ⟨hal-02106642v2⟩

Share

Metrics

Record views

45

Files downloads

221