Exponential lower bounds on the lengths of some classes of branch-and-cut proofs

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.