On the complexity of cutting plane proofs using split cuts

Sanjeeb Dash (sanjeebdus.ibm.com)

Abstract: 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.

Keywords: cutting plane proof, split cut, mixed integer rounding, disjunctive cut, effective interpolation, monotone ciruits

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 10/18/2006
Entry Accepted: 10/18/2006
Entry Last Modified: 06/16/2008

Modify/Update this entry