Optimization Online


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

Thomas Kleinert (thomas.kleinert***at***fau.de)
Martine Labbé (martine.labbe***at***ulb.ac.be)
Fränk Plein (frank.plein***at***ulb.ac.be)
Martin Schmidt (martin.schmidt***at***uni-trier.de)

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

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Complementarity and Variational Inequalities


Download: [PDF]

Entry Submitted: 04/23/2019
Entry Accepted: 04/23/2019
Entry Last Modified: 08/07/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society