Journal
OPERATIONS RESEARCH
Volume 68, Issue 6, Pages 1716-1721Publisher
INFORMS
DOI: 10.1287/opre.2019.1944
Keywords
bilevel optimization; mathematical programs with complementarity constraints (MPCC); bounding polyhedra; big-M; hardness
Funding
- Bavarian State Government
- Deutsche Forschungsgemeinschaft [CRC TRR 154]
- Fonds de la Recherche Scientifique [PDR T0098.18]
Ask authors/readers for more resources
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-Malthough 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-Mdoes 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
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available