New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
CoRR(2024)
摘要
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要