2024/01/24 by Siddharth Prasad, Prasad, Siddharth, Ellen Vitercik +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Optimization and Control (math.OC) #Software Testing and Debugging Techniques #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2401.13773
openalex publication_date 2024/01/24 · openalex created_date 2024/01/27 · openalex updated_date 2026/07/28
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.