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

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.

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.