Article ID Journal Published Year Pages File Type
1142602 Operations Research Letters 2010 6 Pages PDF
Abstract

We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) [20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On the complexity of cutting-plane proofs using split cuts
Authors
,