Volumes of the strong and weak relaxations of the uncapacitated facility-location polytope

Lee, Skipper, and Speakman (2018) asked for formulae or asymptotic expressions for the volumes of the strong and weak relaxations ${\mathcal{P}}_{m,n}\cap {\mathcal{D}}_{m,n}$ and ${\mathcal{Q}}_{m,n}\cap {\mathcal{D}}_{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\to \mathrm{\infty }$, whatever the relative growth of $m$ and $n$. The volume ratio satisfies $Vol({\mathcal{Q}}_{m,n}\cap {\mathcal{D}}_{m,n})\mathrm{/}Vol({\mathcal{P}}_{m,n}\cap {\mathcal{D}}_{m,n})\sim {\prod }_{j=2}^n\text{mleft}(1+\frac{1}{(m-1)j}\text{mright}{)}^m$. From this, we read off the behavior in every growth regime of $m$, and we identify a sharp transition at $m\asymp \ln 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$.