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

  • Oleg A. Prokopyev
  • Ted K. Ralphs
    • Categories Combinatorial Optimization, Game Theory, Other Topics Short URL: https://optimization-online.org/?p=28138

    \(\)

    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.

    Article

    Download

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