New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913208757911552 |
|---|---|
| author | Prasad, Siddharth Vitercik, Ellen Balcan, Maria-Florina Sandholm, Tuomas |
| author_facet | Prasad, Siddharth Vitercik, Ellen Balcan, Maria-Florina Sandholm, Tuomas |
| contents | 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 interesting properties. We derive a broad set of sufficient conditions under which PC lifting is facet defining. To our knowledge, this is 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 our new lifting techniques atop a number of novel cover cut generation routines, which prove to be effective in experiments with CPLEX. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets Prasad, Siddharth Vitercik, Ellen Balcan, Maria-Florina Sandholm, Tuomas Optimization and Control Discrete Mathematics Data Structures and Algorithms 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 interesting properties. We derive a broad set of sufficient conditions under which PC lifting is facet defining. To our knowledge, this is 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 our new lifting techniques atop a number of novel cover cut generation routines, which prove to be effective in experiments with CPLEX. |
| title | New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets |
| topic | Optimization and Control Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.13773 |