Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations

作     者：Buchheim, Christoph 

作者机构：Tech Univ Dortmund Fak Math D-44221 Dortmund Germany 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2023年第51卷第6期

页      面：618-622页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：This work was inspired by discussions held at Dagstuhl Seminar 22441 "Optimization at the Second Level". We thank the anonymous reviewer for many valuable comments that helped to significantly improve the paper 

主　　题：Bilevel linear programming KKT-reformulation NP-completeness 

摘      要：It is a well-known result that bilevel linear optimization is NP-hard. In many publications, reformulations as mixed-integer linear optimization problems are proposed, which suggests that the decision version of the problem belongs to NP. However, to the best of our knowledge, a rigorous proof of membership in NP has never been published, so we close this gap by reporting a simple but not entirely trivial proof. A related question is whether a large enough big M for the classical KKT-based reformulation can be computed efficiently, which we answer in the affirmative. In particular, our big M has polynomial encoding length in the original problem data.(c) 2023 Elsevier B.V. All rights reserved.