This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Dash, S. Search for Related Content

Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs

IBM T. J. Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, New York 10598
sanjeebd{at}us.ibm.com, www.research.ibm.com/people/s/sanjeebd

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 N₀ 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.

Key Words: cutting planes; cutting-plane proofs; branch-and-cut proofs; proof complexity
History: Received: September 27, 2002; revision received: August 10, 2004;revision received: October 4, 2004;