On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization
Oleg A. Prokopyev, Ted K. Ralphs
Operations Research · 2026 · Volume 74 · Issue 4
Abstract
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 N P -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. Funding: This work was supported by the Office of Naval Research [Grants N00014-2-21-2676 and N00014-2-21-2678]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/opre.2024.1411 .
Keywords
Optimization, analysis of algorithms, computational complexity, games/group decisions, noncooperative, mathematics, combinatorics
Enable JavaScript for citation tools and additional paper interactions.