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

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

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

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 2675-2683. https://doi.org/10.24963/ijcai.2025/298

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.
Keywords:
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems
Constraint Satisfaction and Optimization: CSO: Mixed discrete and continuous optimization
Constraint Satisfaction and Optimization: CSO: Solvers and tools
Search: S: Combinatorial search and optimisation