# Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations

arXiv: https://arxiv.org/abs/2307.06639 · HTML: https://mlsanity.com/paper/2307.06639/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2023.

## Built on by (most cited first, 1 of 1)

- [Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms](https://mlsanity.com/paper/2312.17640/) (2023)

## Abstract (arXiv)

It is a well-known result that bilevel linear optimization is NP-hard. In many publications, reformulations as mixed-integer linear optimization problems are proposed, which suggests that the decision version of the problem belongs to NP. However, to the best of our knowledge, a rigorous proof of membership in NP has never been published, so we close this gap by reporting a simple but not entirely trivial proof. A related question is whether a large enough "big M" for the classical KKT-based reformulation can be computed efficiently, which we answer in the affirmative. In particular, our big M has polynomial encoding length in the original problem data.