Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs

Sebastian Berndt, Klaus Jansen, Alexandra Lassota

TL;DR

This paper proves that the 30-year-old theoretical upper bounds for Integer Linear Program (ILP) proximity and sensitivity are tight. By constructing clever, non-negative ILP instances—including one based on the famous Petersen graph—the authors demonstrate that the distance between fractional and integer solutions can indeed reach the worst-case $\Delta^{\Theta(d)}$ scale, even in "natural" settings like Bin Packing.

What Problem Does This Paper Address?

In the world of optimization, Integer Linear Programs (ILPs) are notoriously difficult to solve. A common strategy is to solve the "fractional" version (the LP relaxation) and use it as a guide. Two critical measures define how well this works:

  1. Proximity: How far is the best integer solution from the best fractional solution?
  2. Sensitivity: If we slightly nudge the constraints (the right-hand side $b$), how much does the optimal integer solution jump?

In 1986, Cook et al. established that both measures are bounded by $\Delta^{\Theta(d)}$, where $\Delta$ is the largest entry in the constraint matrix and $d$ is the number of constraints. While these upper bounds have stood for decades, existing lower bounds (examples showing the bounds are "tight") were often unsatisfying—they relied on negative numbers, fractional constraints, or only worked for tiny values of $\Delta$. This paper asks: do these extreme gaps actually occur in "polytopish" ILPs—the kind that arise naturally in combinatorial optimization problems like Bin Packing?

Methods

The authors prove tightness by constructing two specific types of ILP instances that force the solution to explode geometrically.

  • Sensitivity Construction: They design a "staircase" matrix where each row $i$ is linked to row $i+1$ by a factor of $\Delta$. A change of just $1$ in the first constraint ripples through the system, forcing the variables in the optimal solution to shift by powers of $\Delta$ (e.g., $\Delta, \Delta^2, \Delta^3...$).
  • Proximity Construction: This is the paper's most creative leap. They use the Petersen graph to create a structural gap.
The Petersen graph and its six perfect matchings used to construct the proximity lower bound.

By mapping the graph's edges to constraints and its perfect matchings to columns, they create a scenario where a fractional solution can elegantly use "half" of each matching to satisfy constraints perfectly. However, an integer solution is forced to either avoid matchings entirely or pick one and then use a massive number of "slack" variables to fix the resulting imbalances, creating a huge distance between the two optima.

Datasets

Not discussed in the paper. As a theoretical work in computational complexity and discrete geometry, it relies on mathematical proofs and constructive examples rather than empirical datasets.

Key Insights and Ideas

  • Non-negativity Matters: Unlike previous lower bounds, these constructions use only non-negative entries. This is crucial because many algorithmic problems (like scheduling or packing) naturally have non-negative constraints.
  • The Petersen Graph as a "Gap Generator": The authors exploit the fact that every edge in a Petersen graph belongs to exactly two perfect matchings, and any two matchings share exactly one edge. This specific symmetry is what makes the fractional solution "cheap" and the integer solution "expensive."
  • Bin Packing Connection: The authors show that their hard instances are actually subsets of the "Configuration ILP" for the Bin Packing problem. This implies that the standard proximity bounds used to analyze Bin Packing algorithms cannot be improved without specifically accounting for the objective function (minimizing the number of bins).

Key Results

  • Tightness Confirmed: The paper provides the first lower bounds of $\Delta^{\Theta(d)}$ for proximity and sensitivity using non-negative, integral matrices and right-hand sides.
  • Theorem 1 (Sensitivity): For even $d$, there exists a matrix where changing the right-hand side by 1 results in a solution shift of at least $\Delta^{\Theta(d)}$.
  • Theorem 2 (Proximity): For odd $d$, there exists an ILP where the optimal integer solution is at least $\Delta^{\Theta(d)}$ away from the optimal fractional solution.
  • Polytopish Nature: All constructed instances are "polytopish," meaning they represent valid points within a defined polytope, making them highly relevant to real-world algorithmic design.

Limitations and Future Work

The authors note that while these bounds are tight for general ILPs, they might be pessimistic for specific problems if the objective function is taken into account. For example, in the Bin Packing problem, the objective is specifically to minimize the sum of variables ($\min \|x\|_1$). The authors suggest that future research could investigate whether this specific objective function allows for smaller proximity or sensitivity bounds than the general $\Delta^{\Theta(d)}$ worst-case.

Summary updated

Abstract

We consider ILPs, where each variable corresponds to an integral point within a polytope $\mathcal{P}$, i. e., ILPs of the form $\min\{c^{\top}x\mid \sum_{p\in\mathcal P\cap \mathbb Z^d} x_p p = b, x\in\mathbb Z^{|\mathcal P\cap \mathbb Z^d|}_{\ge 0}\}$. The distance between an optimal fractional solution and an optimal integral solution (called proximity) is an important measure. A classical result by Cook et al.~(Math. Program., 1986) shows that it is at most $\Delta^{\Theta(d)}$ where $\Delta$ is the largest coefficient in the constraint matrix. Another important measure studies the change in an optimal solution if the right-hand side $b$ is replaced by another right-hand side $b'$. The distance between an optimal solution $x$ w.r.t.~$b$ and an optimal solution $x'$ w.r.t.~$b'$ (called sensitivity) is similarly bounded, i. e., $\lVert b-b' \rVert_{1}\cdot \Delta^{\Theta(d)}$, also shown by Cook et al. Even after more than thirty years, these bounds are essentially the best known bounds for these measures. While some lower bounds are known for these measures, they either only work for very small values of $\Delta$, require negative entries in the constraint matrix, or have fractional right-hand sides. Hence, these lower bounds often do not correspond to instances from algorithmic problems. This work presents for each $\Delta > 0$ and each $d > 0$ ILPs of the above type with non-negative constraint matrices such that their proximity and sensitivity is at least $\Delta^{\Theta(d)}$. Furthermore, these instances are closely related to instances of the Bin Packing problem as they form a subset of columns of the configuration ILP. We thereby show that the results of Cook et al. are indeed tight, even for instances arising naturally from problems in combinatorial optimization.
BibTeX
@inproceedings{berndt2021tightness,
  author = {Sebastian Berndt and Klaus Jansen and Alexandra Lassota},
  title = {{Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs}},
  booktitle = {SOFSEM},
  year = {2021},
  doi = {10.1007/978-3-030-67731-2\_25},
}
Figure