Linear Programming Hierarchies Collapse under Symmetry
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915611780579328 |
|---|---|
| author | Faenza, Yuri Verdugo, Víctor Verschae, José Villagra, Matías |
| author_facet | Faenza, Yuri Verdugo, Víctor Verschae, José Villagra, Matías |
| contents | 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)$-transitive symmetries--a measure of the underlying symmetry in the problem--the corresponding relaxation at level $k$ of the hierarchy 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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07766 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Programming Hierarchies Collapse under Symmetry Faenza, Yuri Verdugo, Víctor Verschae, José Villagra, Matías Optimization and Control Discrete Mathematics 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)$-transitive symmetries--a measure of the underlying symmetry in the problem--the corresponding relaxation at level $k$ of the hierarchy 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. 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. |
| title | Linear Programming Hierarchies Collapse under Symmetry |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2511.07766 |