On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

• 成果类型: Article
• 署名作者: Prokopyev, Oleg A.; Ralphs, Ted K.
• 署名单位: University of Zurich; Lehigh University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1411
• 发表日期: 2026
• 关键词: analysis of algorithms; computational complexity; games/group decisions; noncooperative; mathematics; combinatorics; reformulations

摘要

We consider the computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader's perspective. We show that, for any constant c > 0, the problem of finding a leader's solution that is within Euclidean distance c(n) of any locally optimal leader's solution, where n is the total number of variables, is NP-hard. Our derivations exploit techniques similar to those used for the analogous result for quadratic optimization problems (QPs). As a side observation, we also provide a BLP reformulation of the celebrated Motzkin-Straus QP model for the maximum clique problem and thereby illuminate the close connection of combinatorial optimization problems to both BLPs and QPs.