  


There's No Free Lunch: On the Hardness of Choosing a Correct BigM in Bilevel Optimization
Thomas Kleinert (thomas.kleinertfau.de) Abstract: One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lowerlevel problem with its KarushKuhnTucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixedinteger linear optimization. The latter step requires to determine some bigM constant in order to bound the lower level's dual feasible set such that no bileveloptimal solution is cut off. In practice, heuristics are often used to find a bigM 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 bilevelcorrect bigM. First, we prove that verifying that a given bigM 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 bigM does not cut off any optimal point of the lower level's dual problem (for any point in the projection of the highpoint 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 Citation: Download: [PDF] Entry Submitted: 04/23/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  