Characterization of the split closure via geometric lifting

DOI10.1016/J.EJOR.2014.12.018MaRDI QIDQ319191zbMATH OpenOpenAlexFDO

Authors Amitabh Basu, Marco Molinaro

Publication date 6 October 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06679

zbMATH Keywords

integer programmingcut-generating functioncutting-planegeometric liftingsplit cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10)

Abstract: We analyze split cuts from the perspective of cut generating functions via geometric lifting. We show that $alpha$-cuts, a natural higher-dimensional generalization of the $k$-cuts of Cornu'{e}jols et al., gives all the split cuts for the mixed-integer corner relaxation. As an immediate consequence we obtain that the $k$-cuts are equivalent to split cuts for the 1-row mixed-integer relaxation. Further, we show that split cuts for finite-dimensional corner relaxations are restrictions of split cuts for the infinite-dimensional relaxation. In a final application of this equivalence, we exhibit a family of pure-integer programs whose split closures have arbitrarily bad integrality gap. This complements the mixed-integer example provided by Basu et al [On the relative strength of split, triangle and quadrilateral cuts, Math. Program. 126(2):281--314, 2011].

Recommendations

• scientific article; zbMATH DE number 2086918
• Split closure and intersection cuts
• On some generalizations of the split closure
• A note on the split rank of intersection cuts
• A note on the MIR closure and basic relaxations of polyhedra

Cites work

• scientific article; zbMATH DE number 3555734 (Why is no real title available?)
• scientific article; zbMATH DE number 2196290 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A geometric perspective on lifting
• A heuristic to generate rank-1 GMI cuts
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• A relax-and-cut framework for Gomory mixed-integer cuts
• Chvátal closures for mixed integer programming problems
• Cut-generating functions
• Disjunctive Programming
• Edmonds polytopes and a hierarchy of combinatorial problems
• Gomory cuts revisited
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Intersection cuts with infinite Split rank
• Mixed integer programming: analyzing 12 years of progress
• On \(t\)-branch split cuts for mixed-integer programs
• On optimizing over lift-and-project closures
• On the relative strength of split, triangle and quadrilateral cuts
• Optimizing over the split closure
• Reduce-and-Split cuts: improving the performance of mixed-integer Gomory cuts
• Split closure and intersection cuts
• Valid inequalities for mixed integer linear programs
• \(k\)-cuts: a variation of Gomory mixed integer cuts from the LP tableau

Cited in

(2)

• A geometric characteristic splitting in all dimensions
• A constructive characterization of the split closure of a mixed integer linear program

This page was built for publication: Characterization of the split closure via geometric lifting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q319191)