Do Unbounded Integrality Gaps Show Up on Real Capacitated Clustering Instances?

Capacitated clustering asks for at most $k$ centers, each serving a limited number of points, chosen to minimize total assignment distance. Theorists have spent a decade on this problem because its standard linear-programming relaxation behaves badly. That relaxation is the version where "open this center" and "assign this point" become fractions instead of yes/no choices, and it can underestimate the true optimal cost by an arbitrarily large factor. This is called an unbounded integrality gap. The theoretical fixes come in two kinds. Pseudo-approximations let the algorithm open slightly more than $k$ centers, or overfill each center by a factor $1+\epsilon$. Strengthened relaxations, such as the rectangle LP and the configuration LP, add constraints that rule out the bad fractional solutions. None of this work has ever been run on data. Every algorithmic paper in this line reports no datasets and no numbers, and the empirical papers on capacitated clustering never compute a lower bound at all.

This proposal measures directly what the theory only bounds in the worst case, on the benchmark instances practitioners actually use. It asks three things. How large is the natural relaxation's gap on these instances? How much does the optimal cost actually fall when a small budget or capacity violation is allowed? Does a column-generation version of the configuration LP produce lower bounds tight enough to certify the solutions that heuristics find? The deliverable is an empirical cost-versus-slack frontier and a practical lower-bounding tool. Together they would tell practitioners whether the worst-case pathology matters for them, and tell theorists which of their relaxations deserves engineering effort.

Core Claim

We hypothesize that the structure driving unbounded gaps is rare and local in realistic instances. That structure is an isolated group of points whose total demand slightly exceeds a multiple of one center's capacity, so the relaxation covers it with "$1+1/u$" fractional centers. If the hypothesis holds, two things follow. The natural relaxation's gap will be modest on telecom and benchmark data and large only where this structure is present. A cheap, restricted configuration LP, solved by column generation rather than the ellipsoid method, will close most of the remaining gap.

We further hypothesize that the cost-versus-slack frontier is far flatter than the worst-case guarantees suggest. Those guarantees are $O(\frac{1}{\epsilon^2}\log\frac{1}{\epsilon})$ for budget violation in Approximating capacitated k-median with (1 + ∊)k open facilities and $O(1/\epsilon^5)$ for capacity violation in Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation. Those two papers prove that relaxing the budget and relaxing capacities are interchangeable in theory. We test whether they are interchangeable in practice.

The central object is the slack frontier. Let $C(\epsilon_k,\epsilon_u)$ denote the optimal integer cost when at most $(1+\epsilon_k)k$ centers may be opened and each center $i$ may serve up to $(1+\epsilon_u)u_i$ points, where $u_i$ is its stated capacity. We measure the two ratios

$$\rho_k(\epsilon)=\frac{C(0,0)}{C(\epsilon,0)},\qquad \rho_u(\epsilon)=\frac{C(0,0)}{C(0,\epsilon)},$$

which say how much cost a practitioner saves by buying slack in each currency. We also measure the gap $C(0,0)/\mathrm{LP}$ for each relaxation. To our knowledge none of these quantities has been reported for any real instance.

Research Program

The first component is exact ground truth. On every instance small enough to solve, we run a mixed-integer programming solver to optimality, or to a certified small gap, for the strict problem and for a grid of slack values $\epsilon\in\{0.02,0.05,0.1,0.2\}$ in each currency. This gives the frontier exactly. Where instances are too large to solve, we report bounds instead.

The second component is a hierarchy of relaxations, each solved on the same instance. At the bottom is the natural LP, which is the one shown to have an unbounded gap even with $(2-\epsilon)k$ centers in On Uniform Capacitated k-Median Beyond the Natural LP Relaxation. Above it is the natural LP strengthened with the solver's own knapsack-cover and flow-cover cuts. Knapsack-cover inequalities are the classical tool for this kind of pathology; Approximation algorithms for the partition vertex cover problem shows how they turn unbounded gaps into bounded ones. At the top is a restricted configuration LP.

Li's configuration LP has variables for every way a small subset of centers $B$ could be opened and filled. We make it practical in two steps. First, we restrict $B$ to single centers and to pairs or triples of mutually close centers. Second, we generate columns on demand. For a single center, finding the most useful new configuration is a knapsack problem over points; with unit demands it reduces to sorting points by reduced cost. For small groups of centers we use exact pricing on small subsets and greedy pricing beyond that. This replaces the ellipsoid-plus-rounding-oracle machinery of the original paper with standard column generation. That machinery is the main reason the configuration LP has never been run. The ablation over the maximum subset size $|B|\in\{1,2,3\}$ isolates how much of the gap closing comes from the multi-center configurations that are Li's key idea.

The third component is a planted-pathology generator. It takes a benign instance and inserts isolated groups of $u+1$ points, following the integrality-gap construction described in the capacitated $k$-median papers above. Varying the number and isolation of these groups lets us test the core claim causally. The natural gap should grow with the planted structure, and the configuration LP should neutralize it. We also compute a simple instance statistic that flags candidate pathological groups: groups whose demand barely exceeds a multiple of nearby capacity and whose distance to the rest of the instance is large. We then check whether this statistic predicts the measured gap on real data.

The fourth component uses the bounds to certify heuristics. For each heuristic solution we report its cost divided by the best available lower bound. That ratio is the per-instance guarantee that local search lacks, the point LP-Based Algorithms for Capacitated Facility Location raises when contrasting LP methods with local search. We do not implement that paper's multi-commodity flow LP or the caterpillar and tree-based roundings for $k$-center (LP Rounding for k-Centers with Non-uniform Hard Capacities, Centrality of trees for capacitated k-center). Those address other objectives, and the proposal is stronger kept to min-sum capacitated $k$-median. They are natural follow-ups if the configuration LP proves useful.

Baselines

The naive reference point has two parts: the natural LP bound, and greedy repair of its rounded solution. If the natural LP's gap is already within a few percent of the exact optimum on real instances, the whole strengthened-relaxation agenda is practically moot. That would be a publishable negative result, and we would report it as such.

The strongest bounding competitor is a commercial MIP solver run on the compact natural formulation with all of its default cutting planes, given the same wall-clock budget as our column generation. Its root bound and its final bound are both recorded. The configuration LP "beats" it only if it gives a strictly higher lower bound at equal time, on instances where the solver does not close the gap, or reaches the solver's bound in clearly less time.

The strongest primal competitor is HA-CCP (HA-CCP: A Hybrid Algorithm for Solving Capacitated Clustering Problem), a variable-neighborhood search with adaptive destruction and reconstruction. Its authors report the best average solution on 58 of 90 instances, the best solution on 30, and an average time of 217.25 seconds on RanReal240/480. One caveat matters for fairness. The CCP suite's native objective is not $k$-median, so these figures are not directly comparable to our objective. We therefore reimplement the HA-CCP neighborhood moves for capacitated $k$-median and run them with the same time budget and random seeds as every other method.

We include Neural Capacitated Clustering (Neural Capacitated Clustering), a graph-neural-network assignment model, as the fast learned baseline on ST, TIM and GMM. Its authors report being 5x to 10x faster than mathematical solvers, with about 90 seconds versus over 900 seconds on some instances. We found no per-instance cost figures for ST or TIM on Lacuna.

For the theoretical pseudo-approximation algorithms themselves, no reported result was found on Lacuna for any dataset. The ablation over the maximum subset size $|B|$ in the configuration LP isolates the proposal's key ingredient.

Why not just…?

Why not just solve the compact MIP with a good solver? This is the real threat. On instances with a few hundred points, branch-and-bound with default cuts may simply find and certify the optimum, which would make strengthened relaxations look academic. We treat this as a hypothesis to test rather than dismiss. The exact-solve component records how the root gap and the time to close it scale from RanReal240 to MDG-a ($n=2000$). Strengthened relaxations matter only if the solver stalls on the larger or planted-pathology instances while column generation keeps a tight bound. If that never happens, we will say so.

Why not just add knapsack-cover or flow-cover cuts to the natural LP? These cuts target exactly the "tiny fraction of a large item" pathology. They may close most of the gap in practice even though they lack Li's worst-case guarantee. The relaxation hierarchy places them as a separate rung precisely so their contribution can be measured apart from that of multi-center configurations. If the $|B|=1$ configuration LP plus cuts matches $|B|=3$, then Li's subset structure adds nothing empirically, which is a meaningful finding.

Why not just run HA-CCP or a neural model and skip bounds entirely? These methods find good solutions, but they cannot say how good. NCC additionally depends on ad hoc dummy clusters to restore feasibility. Without a lower bound, "near optimal" is unverifiable on instances too large for exact solving. The certification experiment quantifies exactly this: how much of the heuristic's apparent quality is confirmed once a tight bound is available.

Proposed Experiments

The data are the CCP suite (RanReal240, RanReal480, RanReal960, MDG-a), with weights interpreted as demands and dissimilarities as assignment costs. Alongside them we use the ST and TIM telecom location data and GMM synthetic points used by NCC, plus planted-pathology variants of each.

The first decisive check is whether the natural gap on real instances is small; we call it small if it stays under about 10% on most instances. If so, and if the gap grows monotonically with the number of planted groups, the core claim is supported. The second check is whether the frontiers $\rho_k(\epsilon)$ and $\rho_u(\epsilon)$ are close to 1 for $\epsilon\le 0.1$. We also test whether they differ systematically: on telecom data with heterogeneous capacities, we expect capacity slack to buy more than budget slack. A difference would show that the theoretical equivalence between the two forms of slack does not translate into equal practical value. The third check is whether the column-generated configuration LP certifies the HA-CCP and NCC solutions to within a few percent on instances where the MIP solver does not finish. The fourth is whether the pathology statistic correlates with the measured gap across real instances.

Each outcome is informative whichever way it falls. Together they answer, for the first time with numbers, whether the decade of work on unbounded gaps describes problems that practitioners actually face.