Strengthening LP Relaxations for Capacitated Optimization Problems

18 concepts14 papers1 proposal

In combinatorial optimization, we often solve hard problems by "relaxing" them into Linear Programs (LPs). We allow variables that should be 0 or 1 to take fractional values like 0.5. If the optimal fractional solution is close to the optimal integer solution, we can usually "round" the fractions to find a good real-world answer.

However, for many problems involving capacities or lower bounds, this approach hits a wall: the unbounded integrality gap. This occurs when the fractional solution is arbitrarily cheaper than the best possible integer solution. When the gap is unbounded, the LP provides no useful information; it is essentially "lying" about the cost of the problem.

The Failure of Natural Relaxations

The "natural" LP relaxation for a problem like the Capacitated Facility Location Problem (CFLP) often fails because it allows the solver to satisfy constraints too cheaply through fragmentation. In CFLP, you must decide which facilities to open and which clients to assign to them, without exceeding a facility's capacity.

As noted by Hyung-Chan An et al. in LP-Based Algorithms for Capacitated Facility Location, the lack of a constant integrality gap in standard LPs historically prevented researchers from using powerful rounding techniques. The LP might open a tiny fraction of many distant facilities to satisfy a single client's demand, resulting in a fractional cost near zero, while any valid integer solution would require opening at least one full facility at high cost.

This phenomenon isn't limited to facility location. Igor Malinovic et al. describe the Min-Knapsack problem as the "evil twin" of the classic Max-Knapsack in On bounded pitch inequalities for the min-knapsack polytope. While Max-Knapsack is well-behaved, Min-Knapsack's natural LP relaxation is plagued by an unbounded gap because the solver can pick tiny fractions of very large items to satisfy a minimum requirement.

Bridging the Gap with Stronger Formulations

To fix an unbounded gap, researchers must "strengthen" the LP by adding new constraints (inequalities) that rule out these unrealistic fractional solutions without excluding any valid integer solutions.

One common strategy is the use of Knapsack Cover (KC) inequalities. In Approximation algorithms for the partition vertex cover problem, Suman Kalyan Bera et al. demonstrate how adding these inequalities can transform a problem with an unbounded gap into one with a tight, logarithmic approximation bound. KC inequalities essentially force the LP to recognize that if a set of items is needed to cover a requirement, the fractional variables must sum to a significant value.

For more complex problems like the Capacitated k-Median, researchers have turned to even more sophisticated structures:

Breaking Long-Standing Stalemates

The transition from unbounded gaps to constant-factor approximations often marks a turning point in a research area. For example, the k-center problem with non-uniform hard capacities saw a 15-year stalemate end when Marek Cygan et al. introduced a rounding technique based on "caterpillar structures" in LP Rounding for k-Centers with Non-uniform Hard Capacities. This proved that even restrictive versions of facility location could be solved within a fixed multiple of the optimal distance.

Similarly, the Lower-Bounded Facility Location (LBFL) problem—where facilities must serve a minimum number of clients—was long considered intractable for LPs. Shi Li eventually provided the first constant-factor approximation in On Facility Location with General Lower Bounds, overcoming the gap that had made previous relaxations ineffective for direct optimization.

Limits of Strengthening

It is important to note that not all gaps can be closed easily. As Babak Behsaz et al. argue in Approximation Algorithms for Minimum-Load k-Facility Location, some problems like Minimum-Load k-Facility Location exhibit large integrality gaps even in sophisticated "configuration-style" LPs. In these cases, the gap is a fundamental signal that the problem requires entirely different algorithmic approaches, such as local search or specialized combinatorial algorithms, rather than simple LP rounding.

Key Foundational Work

LP Rounding for k-Centers with Non-uniform Hard Capacities (2012) — contributed 1 concept elements to this direction.
Improved Approximation Guarantees for Lower-Bounded Facility Location (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unbounded_integrality_gap_2e84ec20,
  title = {unbounded integrality gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unbounded-integrality-gap/rdr_2e84ec20abe34dde8efb2f6305af40f7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_unbounded_integrality_gap_2e84ec20_v1,
  title = {unbounded integrality gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unbounded-integrality-gap/rdr_2e84ec20abe34dde8efb2f6305af40f7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake