Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope
Abstract
Lee, Skipper, and Speakman (2018) asked for formulae or asymptotic expressions for the volumes of the strong and weak relaxations 𝒫m,n∩ 𝒟m,n and 𝒬m,n∩ 𝒟m,n of the uncapacitated facility-location polytope with m facilities and n customers (their Problem~3, ``Texas Hot''). We give exact formulae for all m and n, and we give asymptotics that hold uniformly as m+n→∞, whatever the relative growth of m and n. The volume ratio satisfies Vol(𝒬m,n∩ 𝒟m,n)/Vol(𝒫m,n∩ 𝒟m,n)∼ ∏j=2nmleft(1+1/((m−1)j)mright)m. From this, we read off the behavior in every growth regime of m, and we identify a sharp transition at masympln n. Below it, in a uniformly random point of the strong relaxation, each facility variable is close to $1$ with high probability, and the ratio grows superlinearly in n. Above it, in a uniformly random point of either relaxation, each facility variable is asymptotically uniform on [0,1], and the ratio grows linearly in n.
Related
- A Two-Stage Stochastic Facility Location Problem with Endogenous Demand Learning
- A Solution Method for Single-Source Capacitated Facility Location Problems Under Decision-Dependent Demand Uncertainty
- P-curve: An improved solution for the single-facility location problem in two regions with ℓp- and ℓq-norms
- Relax and Follow: L0-Path Computation with L0-Bregman Relaxations
- Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
BibTeX
@misc{lee2026volumes,
title = {{Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope}},
author = {Jon Lee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25981},
eprint = {2609.25981},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25981},
}
RIS
TY - UNPB
TI - Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope
AU - Jon Lee
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25981
UR - https://arxiv.org/abs/2609.25981
AB - Lee, Skipper, and Speakman (2018) asked for formulae or asymptotic expressions for the volumes of the strong and weak relaxations 𝒫_m,n∩ 𝒟_m,n and 𝒬_m,n∩ 𝒟_m,n of the uncapacitated facility-location polytope with m facilities and n customers (their Problem~3, ``Texas Hot''). We give exact formulae for all m and n, and we give asymptotics that hold uniformly as m+n→∞, whatever the relative growth of m and n. The volume ratio satisfies Vol(𝒬_m,n∩ 𝒟_m,n)/Vol(𝒫_m,n∩ 𝒟_m,n)∼ ∏_j=2^nmleft(1+1/((m−1)j)mright)^m. From this, we read off the behavior in every growth regime of m, and we identify a sharp transition at masympln n. Below it, in a uniformly random point of the strong relaxation, each facility variable is close to $1$ with high probability, and the ratio grows superlinearly in n. Above it, in a uniformly random point of either relaxation, each facility variable is asymptotically uniform on [0,1], and the ratio grows linearly in n.
ER -