Study preserves integrality gaps to improve optimization problem solutions
Integrality gap preserving reductions
Discrete MathematicsData Structures and Algorithms
Summary
Certain mathematical puzzles require finding the best solution from many possibilities. One way to approximate these puzzles is using linear programming, but the difference between the relaxed solution and the actual best can be large, known as the integrality gap. The authors developed a method to shrink the problem’s input while keeping the toughest examples that cause the gaps. This approach helps them calculate exact gaps for smaller problems and improve bounds for scheduling and packing tasks.
What this means in practice
- •For operations research teams: Determine precise limits of linear programming approximations for scheduling and packing problems to guide problem-solving strategies.
- •For software engineers: Improve algorithm design for resource allocation tasks by better understanding when linear programming relaxations yield exact or near-exact solutions.
Authors
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
Abstract
We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.