Linear Programming Hierarchies Collapse under Symmetry
The presence of symmetries is one of the structural features that make some Integer Programs challenging for state-of-the-art solvers. Much research has been devoted to understanding why this happens and which strategies can be implemented to counter the negative effects of symmetry. In this work, I will first review approaches researchers in Integer Programming have undertaken to deal with symmetry. I will then present recent joint work with Victor Verdugo (PUC), Jose Verschae (PUC), and Matias Villagra (Columbia) on the efficacy of Linear Programming (LP) hierarchies in the presence of symmetries. Hierarchies iteratively improve Linear Programming relaxations of Integer Programs and are used to solve Integer Programs both in theory and in practice. In our main result, we show that under $(k+1)$-transitive symmetries–a measure of the underlying symmetry of the problem–the corresponding relaxation at level $k$ of the hierarchy of an integer-empty polytope is non-empty if and only if the initial polytope intersects all $(n-k)$-dimensional faces of the hypercube. In particular, the hierarchies of Sherali-Adams, Lovász-Schrijver, and the Lift-and-Project closure are equally effective at detecting integer emptiness. On the practical side, our result can be used to guide the selecting of cutting planes to improve LP bounds for Integer Programs. On the theoretical side, it provides a unifying, group-theoretic characterization of the poor performance of LP-based hierarchies.
Bio: Yuri Faenza is an associate professor in the IEOR Department at Columbia University, where he is also a member of the Data Science Institute. His research focuses on discrete optimization and market design. His research has been supported by the National Science Foundation (including an NSF Career award), the Air Force Office of Scientific Research, the Office of Naval Research, the Swiss National Science Foundation, and by a Meta Research Award.