Integrality gaps for strengthened linear relaxations of capacitated facility location
Metric uncapacitated facility location is a well studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location (Cfl) is a generalization for which there are local search based constant factor approximations, while there is no known compact relaxation with constant integrality gap. This paper produces, through a host of impossibility results, the first comprehensive investigation of the effectiveness of mathematical programming for metric capacitated facility location, with emphasis on lift and project methods. We show that the relaxations obtained from the natural LP at \varOmega (n)$O(n) levels of the semidefinite Lovasz Schrijver hierarchy for mixed programs, and at \varOmega (n)$O(n) levels of the Sherali Adams hierarchy, have an integrality gap of \varOmega (n)$O(n) where $n$$n is the number of facilities, partially answering an open question of An et al. (Centrality of trees for capacitated k center, 2013) Li and Svensson (Proceedings of 45th ACM Symposium on Theory of Computing, STOC '13. ACM, pp 901 910, 2013) For the families of instances we consider, both hierarchies yield at the $n$$nth level an exact formulation for Cfl. Thus our bounds are asymptotically tight. Building on our methodology for the Sherali Adams result, we prove that the standard Cfl relaxation enriched with the submodular inequalities of Aardal et al. (Math Oper Res 20:562 582, 1995) a generalization of the flow cover valid inequalities, has also an \varOmega (n)$O(n) gap and thus not bounded by any constant. This disproves a long standing conjecture of Levi et al (Math Program 131(1 2):365 379, 2012) We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration style LPs. We characterize the behavior of proper relaxations for Cfl through a sharp threshold phenomenon.
Math. Program.