Linear Programming Hierarchies Collapse under Symmetry
Yuri Faenza, Victor Verdugo, José Verschae, Matías Villagra · 2025
Read Linear Programming Hierarchies Collapse under Symmetry by Yuri Faenza, Victor Verdugo, José Verschae, Matías Villagra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07766.txt.
Introduction
Yuri Faenza, Víctor Verdugo, and José Verschae show when symmetry defeats a standard optimization ladder. Linear programming hierarchies tighten relaxations level by level to crack integer programs. Symmetry is exactly what makes many of those programs hard for solvers, and the authors connect the two facts.
Under highly transitive symmetry, the level-k relaxation is nonempty exactly when the starting polytope meets every face of matching dimension. Whole hierarchies, including famous ones, can therefore collapse at once. The geometry of the initial empty polytope decides fate. Solver builders learn that symmetry must be broken structurally, not merely tightened around, saving wasted effort on doomed relaxations.
Catalog record
| CREATOR | Yuri Faenza, Victor Verdugo, José Verschae, Matías Villagra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07766
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Linear Programming Hierarchies Collapse under Symmetry Yuri Faenza, Victor Verdugo, José Verschae, Matías Villagra Abstract The presence of symmetries is one of the central structural features that make some integer programs challenging for state-of-the-art solvers. In this work, we study the efficacy of Linear Programming (LP) hierarchies in the presence of symmetries. Our main theorem unveils a connection between the algebraic structure of these relaxations and the geometry of the initial integer-empty polytope: We show that under ( k + 1 ) (k+1) -transitive symmetries–a measure of the underlying symmetry in the problem–the corresponding relaxation at level k k of the hierarchy is non-empty if and only if the initial polytope intersects all ( n − k ) (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. Our result provides a unifying, group-theoretic characterization of the poor performance of LP-based hierarchies, and offers a simple procedure for proving lower bounds on the integrality gaps of symmetric polytopes under these hierarchies. 1 Introduction Understanding what makes an Integer Program (IP) challenging for state-of-the-art algorithms is a fundamental step toward developing more effective solvers. While it is reasonable to assume that a larger number of variables and constraints would slow down any algorithm for solving an IP, there are other, more subtle features of IPs that are problematic due to the techniques we currently employ. One such feature is symmetry , informally defined as any transformation of a mathematical object that leaves its fundamental properties unchanged. Mathematicians usually welcome a high degree of symmetry, as it often implies strong properties of the objects under consideration. For instance, systems of linear equalities Ax=b can be solved faster in practice when A=A^{\top} , because factorizations of A are guaranteed to exist in this case, see, e.g., [ 6 ] . In contrast, symmetry is usually problematic in Integer Programming. Even small-sized symmetric problems are often hard to solve [ 17 , 37 , 41 , 40 , 42 ] . In his survey on the topic [ 37 ] , Margot states that the trouble comes from the fact that many subproblems in the enumeration tree are isomorphic, forcing a wasteful duplication of effort –but as we will see, this is not the only problem caused by symmetry. Understanding how to tackle symmetric IPs is essential, as some degree of symmetry is prevalent in both theory and practice. The structure of the problem itself sometimes causes symmetry – for instance, if we wish to schedule jobs on identical machines, or if we solve a combinatorial optimization problem on a highly symmetric graph. Whichever the cause, more than 36% of the instances from MIPLIB 2010 admit nontrivial symmetries; see the work by Pfetsch and Rehn [ 42 ] for details. Moreover, symmetries have played an important role for theoretical work, both from a polyhedral perspective (e.g., [ 48 , 3 ] ), as a devise to construct lower bounds of relaxations (e.g., [ 22 , 34 ] ), and a way of reducing the dimensionality of convex relaxations (e.g., [ 18 , 40 ] ), to mention a few. Our contributions. In this work, we investigate how symmetry can harm state-of-the-art techniques for solving Integer Programs. Our work distinguishes itself from the literature with respect to two features. First, unlike the most common approach of studying the effect of symmetry on creating many “equivalent” integer solutions, we investigate the relationship between symmetry and the performance of linear programming hierarchies , which are well-known techniques that iteratively improve LP relaxations of an integer program. Second, while most research has focused on specific classes of problems such as, e.g., matchings [ 28 , 38 ] , knapsack [ 22 , 27 ] , max-cut and sparsest-cut [ 8 , 23 , 34 ] , scheduling [ 31 , 46 ] , vertex-cover [ 19 ] , and planted clique [ 2 , 39 ] , with the notable exception of the work by Kurpisz et al. [ 30 ] , our assumptions only rely on a well-established group-theoretic parametrization of the symmetry of the underlying polytope, namely k -transitivity . Our main result is the following. Theorem 1.1 . Let k,n\in{\mathbb{N}} such that k<n , and let P\subseteq[0,1]^{n} be a (k+1) -transitive integer-empty polytope. Then the following statements are equivalent: (A) P intersects all of the (n-k) -dimensional faces of the hypercube [0,1]^{n} ; (B) \text{SA}^{k}(P)\neq\emptyset ; (C) \text{LS}^{k}(P)\neq\emptyset ; (D) \text{LS}_{0}^{k}(P)\neq\emptyset . We defer to Section 3 the definition of the hierarchies \text{SA}^{k} , \text{LS}^{k} , and \text{LS}_{0}^{k} . A polytope P is G -invariant for a permutation group G over [n]:=\{1,\ldots,n\} , if under the action of the elements of G , given by \pi x:=(x_{\pi^{-1}(1)},\ldots,x_{\pi^{-1}(n)}) , we have that P=\pi(P) for all \pi\in G . A group G is k -transitive if it can map any ordered sequence of k indices in [n] to any other ordered sequence of k indices in [n] by some element in G . A polytope is k -transitive if it is G -invariant for a k -transitive group G ; observe that (k+1) -transitivity implies k -transitivity. Thus, the larger the k , the more symmetric P is. A high-level description of Theorem 1.1 is as follows. Assume that the polytope P\subseteq[0,1]^{n} is integer-empty and “symmetric enough”, i.e., (k+1) -transitive. Theorem 1.1 implies that we can decide whether k rounds of any of the three hierarchies certify that P is integer-empty just by looking at the intersection of P with the faces of the hypercube [0,1]^{n} . In particular, one of the hierarchies gives us such a certificate if and only if all of them do. It is well-known that, for any k\in\mathbb{N} and polytope P\subseteq[0,1]^{n} , \text{SA}^{k}(P)\subseteq\text{LS}^{k}(P)\subseteq\text{LS}_{0}^{k}(P) , and in general they can be significantly different. In contrast, in our setting, we observe a hierarchy collapse : the three methods are equally effective in determining whether the polytope is integer-empty. This result may explain why the integer-emptiness of symmetric polytopes is hard to prove for LP-based hierarchies: the strongest of the three operators does not outperform the weakest one. Moreover, if the other features stay constant, a “more symmetric” polytope (i.e., k -transitive for larger k ) will “resist” these operators for at least as many rounds as a “less symmetric” polytope. Although the concept of k -transitivity is well-known in group theory–see, e.g., [ 12 , Sec. 7] –we believe that using it as a way of measuring the level of symmetry of a polytope–especially in the context of Integer Programming–is one of the contributions of this work. We briefly discuss in Example 2.2 how our approach can be employed to obtain bounds on the number of rounds the hierarchies need to improve the bound given by an LP relaxation. We further discuss in Appendix A how relaxing some of the hypotheses of Theorem 1.1 makes the statement false. Organization of the paper. In Section 2 , we discuss some applications and consequences of Theorem 1.1 . In Section 3 we introduce the operators that will be used throughout the paper, along with definitions and results on permutation groups that are