Characterization of the split closure via geometric lifting

DOI10.1016/J.EJOR.2014.12.018zbMATH Open1346.90604arXiv1701.06679OpenAlexW2055193102MaRDI QIDQ319191FDOQ319191

Authors: Amitabh Basu, Marco Molinaro 

Publication date: 6 October 2016

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

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

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

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

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)

Cites Work

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

Cited In (2)

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

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)