split cut – Optimization Online

On Polytopes with Linear Rank with respect to Generalizations of the Split Closure

Published: 2021/10/08, Updated: 2021/10/12

Cutting Plane Approaches, Polyhedra cutting planes, integer programming, split closure, split cut, split rank

In this paper we study the rank of polytopes contained in the 0-1 cube with respect to $t$-branch split cuts and $t$-dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$-dimensional 0-1 … Read more

On the complexity of cutting plane proofs using split cuts

Published: 2006/10/18, Updated: 2008/06/16

Sanjeeb Dash

Branch and Cut Algorithms, Cutting Plane Approaches cutting planes, disjunctive cut, effective interpolation, mixed-integer rounding, monotone ciruits, split cut

We prove that cutting-plane proofs which use split cuts have exponential length in the worst case. Split cuts, defined by Cook, Kannan, Schrijver (1993), are known to be equivalent to a number of other classes of cuts, namely mixed-integer rounding (MIR) cuts, Gomory mixed-integer cuts, and disjunctive cuts. Our result thus implies the exponential worst-case … Read more