Split cuts in the plane

2020/03/10 by Basu, Amitabh, Conforti, Michele, Di Summa, Marco +1
#90C10 #90C57 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2003.05022

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.

Related

• Two-halfspace closure
• k-Disjunctive cuts and a finite cutting plane algorithm for general mixed integer linear programs
• Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
• Stabbing Planes
• Learning Cuts via Enumeration Oracles