Thomas R. Puzak, A. Hartstein, et al.
CF 2007
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.
Thomas R. Puzak, A. Hartstein, et al.
CF 2007
Zohar Feldman, Avishai Mandelbaum
WSC 2010
Leo Liberti, James Ostrowski
Journal of Global Optimization
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011