Exponential lower bounds on the lengths of some classes of branch-and-cut proofs
Exponential lower bounds on the lengths of some classes of branch-and-cut proofs
复制标题
DOI：
10.1287/moor.1050.0151
复制
发表时间：
2005-08-01
影响因子：
1.7
通讯作者：
Dash, S
中科院分区：
文献类型：
--
作者：
Dash, S
我们在0 - 1整数规划的背景下研究分支切割证明的复杂性。我们确定了使用0 - 1分支以及提升投影割（一些作者称之为简单析取割）、Gomory - Chvátal割和由Lovász和Schrijver的No矩阵割算子产生的割的分支切割证明长度的指数下界。本文下界结果的一个推论是，上述类型的分支切割方法在最坏情况下具有指数运行时间。
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.