Shashanka Ubaru, Sanjeeb Dash, et al.
NeurIPS 2020
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
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Conference paper
Bonding, interfacial effects and adhesion in dlc
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989