On the Computational Complexity of Bilevel Integer Linear Programming

2026/07/16 by Nagisa Sugishita, Margarida Carvalho
#math.OC

paper · pdf

Abstract

We investigate the computational complexity of bilevel integer linear programming. While Jeroslow~(1985) established that the decision version of this problem is Σ^p₂-complete when restricted to binary variables, we prove that this Σ^p₂-completeness persists even for general integer variables, settling a question that remained open for over 40 years. Furthermore, we analyze the impact of various structural assumptions on computational complexity. Notably, we strengthen the result of Köppe et al.~(2010) by proving polynomial-time solvability whenever the total number of upper- and lower-level variables is fixed, without any additional assumptions.

Related

• Complexity of Bilevel Linear Programming with a Single Upper-Level Variable
• Geometric and computational hardness of bilevel programming
• On the Complexity of Bilevel Linear and Quadratic Programs in Fixed Dimensions
• Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations
• On Integer Programs That Look Like Paths