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

Jon Lee

En palabras de los autores

Lee, Skipper, and Speakman (2018) asked for formulae or asymptotic expressions for the volumes of the strong and weak relaxations $P_{m, n} \cap D_{m, n}$ and $Q_{m, n} \cap 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 \infty$ , whatever the relative growth of $m$ and $n$ . The volume ratio satisfies $V o l (Q_{m, n} \cap D_{m, n}) / V o l (P_{m, n} \cap D_{m, n}) \sim \prod_{j = 2}^{n} \mleft (1 + \frac{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 $m ≍ 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$ .

Resultado principalEl resumen no menciona limitaciones.

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

En palabras de los autores

Más de Optimización ese día

Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions

Optimal Fast Charging of All-Solid-State Batteries under Cathode Transport Constraints

Optimal Control of Traveler Testing in Epidemic Models

Transformer-Informed Trajectory Optimization for Relative Motion in Cislunar Orbits

Maximal Multiplicity Method for Optimal Damping Problem