There's No Free Lunch: On the Hardness of ...
Document type :
Article dans une revue scientifique: Article original
DOI :
Title :
There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization
Author(s) :
Kleinert, Thomas [Auteur]
Friedrich-Alexander Universität Erlangen-Nürnberg = University of Erlangen-Nuremberg [FAU]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Plein, Fränk [Auteur]
Université libre de Bruxelles [ULB]
Schmidt, Martin [Auteur]
Trier Universität = Trier University = Université de Trèves [Uni Trier]
Friedrich-Alexander Universität Erlangen-Nürnberg = University of Erlangen-Nuremberg [FAU]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Plein, Fränk [Auteur]
Université libre de Bruxelles [ULB]
Schmidt, Martin [Auteur]
Trier Universität = Trier University = Université de Trèves [Uni Trier]
Journal title :
Operations Research
Publisher :
INFORMS
Publication date :
2020
ISSN :
0030-364X
English keyword(s) :
Bilevel optimization
Mathematical programs with complementarity constraints (MPCC)
Bounding polyhedra
Big-M
Hardness
Mathematical programs with complementarity constraints (MPCC)
Bounding polyhedra
Big-M
Hardness
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
English abstract : [en]
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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-03137942/document
- Open access
- Access the document
- https://dipot.ulb.ac.be/dspace/bitstream/2013/316639/3/2019-06-17-preprint-version.pdf
- Open access
- Access the document
- https://hal.inria.fr/hal-03137942/document
- Open access
- Access the document
- https://hal.inria.fr/hal-03137942/document
- Open access
- Access the document
- document
- Open access
- Access the document
- bilevel-lp-lp-bigm-hardness_preprint.pdf
- Open access
- Access the document
- 2019-06-17-preprint-version.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- bilevel-lp-lp-bigm-hardness_preprint.pdf
- Open access
- Access the document