We consider the theoretical 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.
Citation
COR@L Technical Report 24T-015, Lehigh University.