Compact Constant-Gap Relaxations for Capacitated Facility Location

Repeated facility-location question: two invalid compactness shortcuts

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

Capacitated facility location opens facilities and assigns clients while respecting capacities and minimizing opening and connection costs. Polynomial size means that the number of encoded variables and inequalities is polynomial in instance size.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: This extraction repeats the capacitated-facility-location relaxation question represented canonically by OWR-13353-021. No separate clean statement is promoted, and the original record remains visible for provenance.

Related catalogue records: 30002732. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

Does there exist a polynomial-size linear-programming relaxation for the capacitated facility location problem whose integrality gap is bounded by a constant? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

The supplied fragment concerns duplicate Constant-Gap Facility-Location Relaxation. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002733 (OWR-13353-022). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2015$, Oberwolfach Reports, DOI 10.4171/owr/2014/51, pp. 2873--2932 https://doi.org/10.4171/owr/2014/51.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Does there exist a polynomial-size linear-programming relaxation for the capacitated facility location problem whose integrality gap is bounded by a constant?

Source-record scope

This is the preserved duplicate of catalogue ID 30002732, with upstream unrecoverable-extraction metadata. The primary report's printed page 2921 contains one compact constant-gap facility-location question, following the separate exact-gap question. We do not treat this repeated ID as another independent conjecture. This standalone attempt tests two shortcuts relevant to that same question; it does not reconstruct an additional missing target.

An exponential number of facets need not prevent an extension

A possible negative route is to exhibit exponentially many essential projected inequalities and conclude that no compact extended formulation exists. The inference is false. For $d\ge2$, consider \[ C_d=\{x\in\mathbb R^d:\sum_{i=1}^d|x_i|\le1\} =\{x:s^Tx\le1\ \text{for every }s\in\{-1,1\}^d\}. \] Equality of the descriptions follows by choosing $s_i$ with the sign of $x_i$; all other sign sums are no greater than the sum of absolute values. For each $s$, the $d$ points $s_i e_i$ belong to the hyperplane $s^Tx=1$ and to $C_d$. They are affinely independent: a relation $\sum_i a_i s_i e_i=0$ forces every $a_i=0$, in particular every affine relation with $\sum_i a_i=0$ is trivial. Thus this is a facet, since its affine dimension is $d-1$. The polytope is full dimensional because it contains a neighborhood of zero. Different signs give different facets, so there are $2^d$ of them. None can be deleted from this sign description: for any $1<t<d/(d-2)$ when $d>2$, or any $t>1$ when $d=2$, $x=(t/d)s$ violates its own inequality while every different sign vector $u$ has $u^Tx\le t(d-2)/d<1$.

Yet $C_d$ is the projection of just $2d+1$ inequalities in $2d$ variables: \[ t_i\ge x_i,\quad t_i\ge-x_i\quad(1\le i\le d),\qquad\sum_it_i\le1. \] These imply $\sum_i|x_i|\le\sum_it_i\le1$, and conversely one may set $t_i=|x_i|$. Thus facet counting in the original variables alone cannot settle the source's unrestricted compact-formulation question. This familiar example is a proof of a failed inference, not a facility-location lower bound.

Why one residual total-flow condition loses a source constraint

The MFN network in the source includes a commodity-specific terminal arc of capacity $y_i d_j$. Replacing it by an unlimited terminal arc appears to simplify each residual feasibility check. The following exact scenario shows what information is lost, even before attempting to compress all scenarios. There are $N=U+1$ clients, $U\ge1$, and facilities $A,B$ of capacities $U,N$. Take $y_A=1,y_B=1/N$, $x_{Aj}=U/N,x_{Bj}=1/N$ for every client. Partially assign $U$ clients fully to $A$, leaving $j_0$ unassigned. Facility $A$ then has zero residual capacity, while $B$ has residual capacity $Ny_B=1$. If terminal bounds are removed, the one residual unit is routable: send $1/N$ directly from $j_0$ to $B$, and send $1/N$ along each of the $U$ paths $j_0,A,j,B$ through a preassigned client $j$. The total first-arc load $j_0\to A$ is $U/N$, every reverse arc $A\to j$ has capacity one, and every $j\to B$ arc carries $1/N$, exactly its assignment capacity. The resulting unit crosses $B\to B'$ and reaches $j_0^t$.

In the actual MFN system, however, the arc $B'\to j_0^t$ has capacity $y_Bd_{j_0}=1/N<1$, and the $A$ bridge has zero capacity. The residual unit cannot reach its sink. Thus this weakened check accepts a scenario rejected by the source relaxation. The example does not prove that the weakened formulation passes every other partial assignment, nor that all single-commodity formulations have a large gap. It pinpoints the failure of the proposed deletion in a specific required check.

Context and adversarial audit

The natural-encoding restriction in the primary abstract arXiv:1312.1819 was inspected separately from the original report. Neither a count of MFN scenarios nor that restricted lower-bound statement excludes all polynomial extensions. Conversely, the residual-flow calculation does not manufacture a compact constant-gap LP. The duplicate remains the same unresolved source question. The audit checked affine independence of the facet witnesses, the $d=2$ boundary, every arc in the residual routing, and the distinction between a single residual scenario and universal feasibility. No computation, theorem prover, novelty claim or independent human proof checking is asserted.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The repeated compact-relaxation target remains unresolved; facet counting and deleting the commodity-specific residual bound do not establish either a compact formulation or its impossibility.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 51/2014, Svensson, LP-based algorithms for capacitated facility location, printed pp. 2919--2921; original questions and scope read. https://doi.org/10.4171/owr/2014/51.
• An, Singh and Svensson, LP-Based Algorithms for Capacitated Facility Location, arXiv:1407.3263v2; introduction and Section 2, especially Definition 2.1 and the partial-assignment network, inspected. The general approximation proof is not independently checked here. https://arxiv.org/html/1407.3263.
• Kolliopoulos and Moysoglou $2013$; primary abstract inspected for the natural-encoding qualifier only. https://arxiv.org/abs/1312.1819.

Final status

Unresolved in this attempt. The repeated compact-relaxation target remains unresolved; facet counting and deleting the commodity-specific residual bound do not establish either a compact formulation or its impossibility.

Compact facility-location formulations: exact enumeration and the missing compression

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

Capacitated facility location opens facilities and assigns clients while respecting capacities and minimizing opening and connection costs. Polynomial size means that the number of encoded variables and inequalities is polynomial in instance size.

A relaxation contains the integral feasible solutions. For a nonnegative minimization objective, its integrality gap is the supremum of the ratio between the integral optimum and the relaxation optimum over the specified instances.

A linear program optimizes $c^Tx$ over a polyhedron $\{x:Ax\leq b\}$. In the simplex method a pivot moves between adjacent basic feasible solutions; a pivot rule chooses the next such move.

Statement recorded in the supplied source.

Does there exist a polynomial-size linear-programming relaxation for the capacitated facility location problem whose integrality gap is bounded by a constant? [S2]

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Find a compact linear relaxation that approximates every capacitated facility-location instance within a constant factor.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002732 (OWR-13353-021). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2015$, Oberwolfach Reports, DOI 10.4171/owr/2014/51, pp. 2873--2932 https://doi.org/10.4171/owr/2014/51.
• S3 Kao, MFN integrality gap https://doi.org/10.1137/1.9781611977554.ch40.
• S4 lower bounds for compact formulations https://arxiv.org/abs/1312.1819. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Does there exist a polynomial-size linear-programming relaxation for the capacitated facility location problem whose integrality gap is bounded by a constant?

Attempt to encode all opening choices

We retain the source's metric capacitated problem with unit clients, integer capacities, and at most one opening per facility. Let $m$ be the number of facilities and $n\ge1$ the number of clients. Replace each capacity $U_i$ by $\min(U_i,n)$; no feasible assignment or optimum changes. For a fixed opened subset $S$, consider the assignment polytope \[ P_S=\left\{z\ge0:\ \sum_{i\in S}z_{ij}=1\ (j=1,\ldots,n),\quad \sum_j z_{ij}\le U_i\ (i\in S)\right\}. \] It is nonempty exactly when $\sum_{i\in S}U_i\ge n$: necessity follows by summing, and sufficiency follows by assigning successive clients to successive available slots. Thus feasibility of the opened subset itself is elementary; connection costs are still tied to the facility locations.

Complete assignment integrality proof.

Every point of $P_S$ is a convex combination of integral assignments. Add one dummy client row with entries $r_i=U_i-\sum_j z_{ij}$. In the resulting nonnegative matrix, each facility column sums to the integer $U_i$, each real client row sums to one, and the dummy row sums to the integer $\sum_iU_i-n$. If any entry is nonintegral, form the bipartite graph of nonintegral entries between rows and columns. At every incident vertex, there must be at least two such entries: an integer row or column sum cannot have just one nonintegral summand. A finite graph with minimum degree at least two contains a cycle (extend a nonbacktracking walk until a vertex repeats); bipartiteness makes its length even. Add an alternating increment $t,-t$ along this cycle. Both signs are feasible for sufficiently small $t>0$, preserving all margins. In each direction increase $t$ until an entry hits its adjacent integer, without crossing any integer on the cycle. The original matrix is a strict convex combination of these two endpoints, and each endpoint has fewer nonintegral entries. Recurse on each endpoint. The depth is bounded by the number of entries, so this is a finite convex decomposition into integral nonnegative matrices. Deleting the dummy row yields integral assignments; a real row with sum one has exactly one entry one. This proves the assertion without appealing to an external matching integrality theorem.

An exact extended formulation.

For each capacity-feasible subset $S$ introduce $\lambda_S\ge0$ and variables $z^S_{ij}\ge0$ for $i\in S$, with \[ \sum_S\lambda_S=1,\quad \sum_{i\in S}z^S_{ij}=\lambda_S,\quad \sum_j z^S_{ij}\le U_i\lambda_S,\quad y_i=\sum_{S\ni i}\lambda_S,\quad x_{ij}=\sum_{S\ni i}z^S_{ij}. \] If $\lambda_S=0$, nonnegativity and the client equalities force $z^S=0$. Otherwise $z^S/\lambda_S\in P_S$ and has the integral decomposition just proved. Hence every projected $(x,y)$ is a convex combination of feasible integral facility-location solutions with exactly the opened sets $S$. Conversely, an integral solution is represented by putting its subset's $\lambda$ equal to one; convex combinations remain feasible. This proves equality with the integral convex hull, including facilities opened but unused. Minimizing the usual linear cost over this formulation has gap one, because a convex combination's cost is the same combination of integral costs and cannot be smaller than their minimum.

The precise missing step

This construction uses $O(2^m mn)$ variables and inequalities. It is polynomial for fixed $m$, and also for $m\le C\log_2 n$ with fixed $C$, but not for unrestricted $m$. Binary coefficient sizes remain polynomial: $U_i\le n$ and all other coefficients are zero or one. The source asks for a polynomial bound in the unrestricted instance size; our subset enumeration does not supply it.

An attempted compression retaining only each subset's total capacity loses the connection objective even in the smallest metric instance. On the real line place one client at $\varepsilon$, facility $a$ at zero and facility $b$ at $R>2\varepsilon$, with unit capacities and zero opening costs. The sets $\{a\}$ and $\{b\}$ have the same total capacity, but their optimal connection costs are $\varepsilon$ and $R-\varepsilon$ respectively. Their ratio is unbounded as $R/\varepsilon$ grows. Thus this proposed capacity-only state cannot substitute for the subset while preserving its cost information. This does not rule out more sophisticated extended variables.

Source check and adversarial audit

The OWR question explicitly distinguishes exponentially many constraints from a polynomial-size formulation. The inspected Kolliopoulos--Moysoglou abstract, arXiv:1312.1819, restricts its lower bound to the natural facility- location encoding; it does not establish a lower bound for all extensions. Its full proof is not used here. The known-style disjunctive construction above is provided with a complete elementary proof and no novelty claim. The audit checked zero multipliers, empty infeasible subsets, unused openings, capacity truncation, and finite termination of the convex decomposition. No numerical or formal proof checking was performed for this record.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. An exact exponential-size formulation and restricted-size cases are established, but no polynomial-size constant-gap relaxation for unrestricted facility count or extension-complexity obstruction is obtained.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 51/2014, Svensson, LP-based algorithms for capacitated facility location, printed pp. 2919--2921; original questions and scope read. https://doi.org/10.4171/owr/2014/51.
• An, Singh and Svensson, LP-Based Algorithms for Capacitated Facility Location, arXiv:1407.3263v2; introduction and Section 2, especially Definition 2.1 and the partial-assignment network, inspected. The general approximation proof is not independently checked here. https://arxiv.org/html/1407.3263.
• Kolliopoulos and Moysoglou, Exponential lower bounds on the size of approximate formulations in the natural encoding for Capacitated Facility Location $2013$; abstract and natural-encoding restriction inspected, proof not rederived. https://arxiv.org/abs/1312.1819.

Final status

Unresolved in this attempt. An exact exponential-size formulation and restricted-size cases are established, but no polynomial-size constant-gap relaxation for unrestricted facility count or extension-complexity obstruction is obtained.