On the complexity of cutting-plane proofs using split cuts

On the complexity of cutting-plane proofs using split cuts

0.00 Avg rating0 Votes
Article ID: iaor20101721
Volume: 38
Issue: 2
Start Page Number: 109
End Page Number: 114
Publication Date: Mar 2010
Journal: Operations Research Letters
Authors:
Keywords: cutting plane algorithms
Abstract:

We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997), 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.

Reviews

Required fields are marked *. Your email address will not be published.