J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Paper
On the complexity of cutting-plane proofs using split cuts
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. © 2009 Elsevier B.V.
Related
George Markowsky
J. Math. Anal. Appl.
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011