论文标题
分支和切割平面的复杂性在混合构成优化中-II
Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
论文作者
论文摘要
我们从理论的角度研究切割平面和分支方案的复杂性。我们为经验观察到的现象提供了一些严格的基础，即将切割平面和分支结合到分支切割框架中可能是比单独使用这些工具要高的数量级。特别是，我们给出了一般条件，在该条件下，切割平面策略和分支方案在将分支切割成效率时可证明具有指数优势。这些算法的效率是使用两种具体度量进行评估的：中间线性/凸程序中使用的约束的迭代次数和稀疏性。据我们所知，我们的结果是第一个在数学上严格的证明分支和切割比纯切割平面和纯分支和结合的优势。
We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. In particular, we give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. To the best of our knowledge, our results are the first mathematically rigorous demonstration of the superiority of branch-and-cut over pure cutting planes and pure branch-and-bound.
