论文标题
分支机构和切割平面的复杂性
Complexity of branch-and-bound and cutting planes in mixed-integer optimization
论文作者
论文摘要
我们研究了分支机构（BB）和切割平面（CP）算法的理论复杂性，以进行混合智能优化。特别是，当两者都基于相同的分离族时，我们研究了BB和CP的相对效率。我们将破折号的结果扩展到非线性设置，该设置表明，对于凸0/1问题，CP至少与BB相同，并且具有可变的分离。我们通过给出稳定的设置问题的实例来提高这一点，我们可以证明CP比BB更好。我们进一步表明，如果一个人远离0/1组，那么CP比BB的优势消失了。在有示例中，BB在O（1）时间内完成，但是CP花费无限长时间才能证明最佳性，并且指数型才能任意接近最佳值（对于可变分离）。接下来，我们表明，如果将尺寸视为固定常数，那么无论使用哪种析取率家族，情况都会逆转和BB至少与CP一样（直至多项式爆炸）。此差距是指数级的示例（在输入数据的大小）中也可以补充。
We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by giving instances of the stable set problem where we can provably establish that CP does exponentially better than BB. We further show that if one moves away from 0/1 sets, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). We next show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up), no matter which family of disjunctions is used. This is also complemented by examples where this gap is exponential (in the size of the input data).
