New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets

Prasad, Siddharth; Vitercik, Ellen; Balcan, Maria-Florina; Sandholm, Tuomas

doi:10.24963/ijcai.2025/298

New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets

Siddharth Prasad, Ellen Vitercik, Maria-Florina Balcan, Tuomas Sandholm

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 2675-2683.

https://doi.org/10.24963/ijcai.2025/298

Keywords

Constraint Satisfaction and Optimization: CSO: Mixed discrete and continuous optimization
Search: S: Combinatorial search and optimisation
Constraint Satisfaction and Optimization: CSO: Solvers and tools
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems

Abstract

Sequence-independent lifting is a procedure for strengthening valid inequalities of an integer program. We generalize the sequence-independent lifting method of Gu, Nemhauser, and Savelsbergh (GNS lifting) for cover inequalities and correct an error in their proposed generalization. We obtain a new sequence-independent lifting technique---piecewise-constant (PC) lifting---with a number of important properties. We derive a broad set of sufficient conditions under which PC lifting yields facets---the first characterization of facet-defining sequence-independent liftings that are efficiently computable from the underlying cover. Finally, we demonstrate via experiments that PC lifting can be a useful alternative to GNS lifting. We test PC lifting atop a number of novel cover inequality generation routines, which prove to be effective in experiments with CPLEX. PC lifting delivers strong numerical properties making it practically relevant for integer programming solvers.

Siddharth Prasad, Ellen Vitercik, Maria-Florina Balcan, and Tuomas Sandholm. 2025. New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 2675–2683. https://doi.org/10.24963/ijcai.2025/298

@inproceedings{ijcai2025p298,
  title     = {New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets},
  author    = {Prasad, Siddharth and Vitercik, Ellen and Balcan, Maria-Florina and Sandholm, Tuomas},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {2675--2683},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/298},
  url       = {https://doi.org/10.24963/ijcai.2025/298},
}

TY  - CPAPER
TI  - New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets
AU  - Prasad, Siddharth
AU  - Vitercik, Ellen
AU  - Balcan, Maria-Florina
AU  - Sandholm, Tuomas
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 2675
EP  - 2683
DO  - 10.24963/ijcai.2025/298
UR  - https://doi.org/10.24963/ijcai.2025/298
ER  -