Standard bounds for mixed-integer bilevel programs cannot be consistently improved
On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs
Computational Complexity
Summary
Mixed-integer bilevel linear programs are complicated optimization problems involving two decision-makers, one acting first and the other reacting. People usually start solving these by relaxing the problem to a simpler one, ignoring the second decision-maker’s optimal choice. The authors show that for broad classes of these problems, this standard simpler version cannot be improved efficiently in a general way, unless major breakthroughs in computational theory occur. This means current methods for getting bounds in these problems are essentially as good as possible from a complexity perspective.
What this means in practice
- •For optimization software developers: Avoid pursuing uniform polynomial-time improvements for standard bilevel relaxation bounds since this paper proves their theoretical impossibility under common complexity assumptions.
- •For operations research engineers: Design bilevel optimization algorithms understanding that iterative mixed-integer linear programming methods cannot guarantee uniform improvements over standard relaxation bounds.
A theory result. No direct application yet.
Authors
Sergey S. Ketkov, Oleg A. Prokopyev
Abstract
Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.