Split cuts in the plane

DOI10.1137/20M1324521MaRDI QIDQ5147031zbMATH OpenOpenAlexFDO

Authors Amitabh Basu, Michele Conforti, Marco Di Summa, Hongyi Jiang

Publication date 2 February 2021

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

cutting planesinteger programmingsplit cuts

Mathematics Subject Classification ID

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

Abstract: We provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane has polynomial size.

Recommendations

• scientific article; zbMATH DE number 2086918
• On the complexity of cutting-plane proofs using split cuts
• On the separation of split cuts and related inequalities
• Fenchel Cutting Planes for Integer Programs
• Split closure and intersection cuts

Cites work

• A linear algorithm for integer programming in the plane
• Chvátal closures for mixed integer programming problems
• Computing Two-Dimensional Integer Hulls
• Cutting Planes and the Elementary Closure in Fixed Dimension
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Integer Programming
• On finitely generated closures in the theory of cutting planes
• On the Chvátal-Gomory closure of a compact convex set
• Split closure and intersection cuts
• The split closure of a strictly convex body
• The triangle closure is a polyhedron

Cited in

(3)

• Complexity of branch-and-bound and cutting planes in mixed-integer optimization
• CUTTING PLANE WITH NON-UNIFORM DISTRIBUTIONS
• Complexity of optimizing over the integers

This page was built for publication: Split cuts in the plane

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