On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs

1. Introduction

• The paper studies optimistic MIBLPs, selecting the leader-preferred solution among follower optima, and assumes the leader’s feasible set has no coupling constraints.Source: §1 · p. 2

1.1. Single-Level Relaxation

• Dropping follower optimality defines the SLR and gives a valid lower bound; without coupling constraints, pairing an SLR-optimal leader solution with a follower-optimal response gives an upper bound.Source: §1.1 · p. 3
• The research question is whether both standard bounds admit strict, uniform alternatives computable in the same complexity regime for every instance in a problem class.A bound is called provably best when no such uniform alternative exists.Source: §1.1 · p. 4

1.2. Our Contributions

• For min-max BLPs, unless P = NP, the SLR lower bound and the lower bound from the KKT-based MILP’s LP relaxation are provably best.Source: §1.2 · p. 5
• When SLR has multiple leader-optimal solutions, computing its tightest associated upper bound is NP-hard; even when uniquely defined, that bound is provably best unless P = NP.Source: §1.2 · p. 5
• Under standard regularity assumptions, the SLR-based bounds’ gap decreases at least linearly with the distance between leader and follower objective vectors, and both converge as the objectives align.This approximation result also applies to pure integer IBLPs.Source: §1.2 · p. 5
• The linear programming relaxation of the SLR is a provably best polynomial-time computable lower bound (Theorem 5).Source: §1.2 · p. 6
• The standard lower bound z*_SLR is best among lower bounds computable in polynomial time with access to an MILP oracle (Theorem 6).Source: §1.2 · p. 6
• The analogous no-improvement result holds for the associated SLR-based upper bound, even when it is uniquely defined (Theorem 7).Source: §1.2 · p. 6
• Under standard complexity-theoretic assumptions, no generic decomposition or cutting-plane framework can systematically strengthen the standard SLR-based bounds in polynomially many iterations.The results do not rule out stronger bounds for particular instances or more restrictive MIBLP classes.Source: §1.2 · p. 6

2. Bilevel Linear Programs

• Under A1, BLP and its SLR have finite optima; BLP is strongly NP-hard even for min-max problems, while its SLR bounds are polynomial-time computable.The bounds are polynomial-time computable because the SLR and follower’s problem reduce to linear programs when n2 = m2 = 0.Source: §2 · p. 7

2.1. Lower Bounds

• The SLR lower bound is provably best even for min-max BLPs, barring a polynomial-time strict uniform improvement.The result is established under the paper’s complexity assumption that P ≠ NP.Source: §2.1 · p. 8
• Even the KKT-based LP lower bound is provably best when the KKT reformulation is exact and the lower-bound theorem’s assumptions hold.A sufficiently large valid M with polynomial encoding size is available, and the KKT relaxation supplies another valid lower bound.Source: §2.1 · p. 10

2.2. Upper Bounds

• With unique SLR and follower optima, the tightest upper bound is polynomial-time computable yet provably best even for min-max BLPs.When optimal solutions are not unique, the upper bound defined by equation (5) may itself be nonunique; computing the tightest upper bound is NP-hard even for min-max BLPs.Source: §2.2 · pp. 10, 11, 13
• Under Assumption A1 and unique optima for the SLR and associated follower problem, no polynomial-time computable upper bound can strictly dominate the tightest SLR-based upper bound unless P = NP.Source: §2.2 · pp. 14, 16

2.3. Approximation guarantees for SLR-based bounds

• When the BLP itself is polynomially solvable, it provides polynomial-time improvements to the SLR-based bounds; the SLR is exact for min-min problems with g=d.Source: §2.3 · p. 16
• Computing D over a polyhedron is NP-hard in general, but with the ℓ1 primal norm (ℓ∞ dual), D is polynomial-time computable by solving 2m1 linear programs.Source: §2.3 · p. 17
• Theorem 4 shows the gap between SLR-based lower and upper bounds decreases at least linearly with ||d-g||, and they are exact when g=d.Source: §2.3 · p. 17
• The approximation result does not rely on continuous leader or follower variables and applies to pure integer problems under standard regularity assumptions.Source: §2.3 · p. 17

3. Integer Bilevel Linear Programs

• In IBLPs, computing both the SLR lower bound and its associated upper bound is NP-hard.The section considers problems in which both leader and follower solve integer linear programs.Source: §3 · p. 18
• The continuous relaxation of the SLR is a polynomial-time-computable, valid but generally weaker lower bound, and its possibly fractional optimum cannot provide a valid upper bound.These properties motivate testing whether this relaxation can be uniformly improved in polynomial time.Source: §3 · pp. 18–19

3.1. Polynomial-time Computable Lower Bounds

• The continuous-relaxation lower bound is provably unimprovable in polynomial time, even for min-max IBLPs.The result rules out a uniform polynomial-time improvement for the class considered in this subsection.Source: §3.1 · p. 19

3.2. MILP-Oracle Computable Lower Bounds

• Under the stated complexity assumption, no polynomial-time algorithm with an MILP oracle uniformly improves the SLR lower bound, even for min-max IBLPs.This rules out systematic improvement through iterative MILP-based procedures, including approaches that repeatedly add valid inequalities and solve polynomial-size MILPs.Source: §3.2 · pp. 20–21

3.3. MILP-Oracle Computable Upper Bounds

• Under the stated complexity assumption, the associated upper bound is provably unimprovable by an MILP-oracle algorithm for min-max IBLPs when the SLR and follower problem have unique optima.The result concerns classes where both optimization problems admit unique optimal solutions.Source: §3.3 · p. 22
• The proof’s constructed upper-bound value is U if and only if QSAT2 admits a yes instance.Source: §3.3 · p. 23
• Theorems 6 and 7 show that min-max IBLP SLR-based lower and upper bounds cannot be uniformly improved by polynomial-time MILP-oracle algorithms unless the polynomial hierarchy collapses.The result rules out systematic strengthening within this computational framework.Source: §3.3 · p. 23
• Unless the polynomial hierarchy collapses, no generic MILP-based decomposition or cutting-plane framework can strengthen these bounds within polynomially many iterations.Source: §3.3 · p. 23

• For continuous and pure integer bilevel linear programs, uniform improvements are generally impossible within the respective computational regimes, even for min-max problems.Source: §4 · p. 24
• The gap between standard lower and upper bounds decreases at least linearly as the leader’s and follower’s objective vectors become aligned.Source: §4 · p. 24
• Although standard bounds can be weak for individual instances, uniformly stronger bounds cannot generally be obtained at comparable computational cost.Source: §4 · p. 24
• These results do not rule out stronger bounds for particular instances or more restrictive problem classes.Identifying structural conditions that permit such improvements is a direction for future research.Source: §4 · p. 24