On the complexity of cutting plane proofs using split cuts

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

Branch and Cut Algorithms, Cutting Plane Approaches cutting planes, disjunctive cut, effective interpolation, mixed-integer rounding, monotone ciruits, split cut Short URL: https://optimization-online.org/?p=9078

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 complexity of cutting-plane proofs which use the above cuts.

Article

Download

View On the complexity of cutting plane proofs using split cuts