Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We establish an exponential lower bound on the length of branch-and-cut proofs that use 0-1 branching and lift-and-project cuts (called simple disjunctive cuts by some authors), Gomory-Chvátal cuts, and cuts arising from the N0 matrix-cut operator of Lovász and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential running time in the worst case. © 2005 INFORMS.
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
G. Ramalingam
Theoretical Computer Science
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
Raymond F. Boyce, Donald D. Chamberlin, et al.
CACM