---
title: "New Sequence-Independent Lifting Techniques for Cover Inequalities and When They Induce Facets"
authors:
  - "Siddharth Prasad"
  - "Ellen Vitercik"
  - "Maria-Florina Balcan"
  - "Tuomas Sandholm"
doi: "10.24963/ijcai.2025/298"
url: "https://ijcai.org/proceedings/2025/298"
pdf: "https://ijcai.org/proceedings/2025/0298.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "2675-2683"
track: "Main Track"
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"
---

# 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*, pages 2675-2683. DOI: [10.24963/ijcai.2025/298](https://doi.org/10.24963/ijcai.2025/298)

## 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.