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

• 成果类型: Article
• 署名作者: Dash, S
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0151
• 发表日期: 2005
• 页码: 678-700
• 关键词: cutting-plane proofs; programming-problems; BOOLEAN FUNCTIONS; integer programs; complexity; inequalities; relaxations; RESOLUTION; closures; size

摘要

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-Chvatal cuts, and cuts arising from the No matrix-cut operator of Lovasz 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.