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

• 成果类型: Article
• 署名作者: Kleinert, Thomas; Labbe, Martine; Plein, Fraenk; Schmidt, Martin
• 署名单位: University of Erlangen Nuremberg; Universite Libre de Bruxelles; Universitat Trier
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1944
• 发表日期: 2020
• 页码: 1716-1721
• 关键词: linear bilevel; electricity; branch; MODEL

摘要

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.