Complexity of branch-and-bound and cutting planes in mixed-integer optimization
Complexity of branch-and-bound and cutting planes in mixed-integer optimization
复制标题
混合整数优化中分支定界和割平面的复杂性
DOI：
10.1007/s10107-022-01789-5
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Jiang, Hongyi
中科院分区：
文献类型：
--
作者：
Basu, Amitabh;Conforti, Michele;Di Summa, Marco;Jiang, Hongyi
研究了求解混合整数优化问题的分支定界（BB）和割平面（CP）算法的理论复杂性。特别是，我们研究了BB和CP的相对效率，当两者都是基于同一个家庭的析取。我们扩展了Dash（International Conference on Programming and Combinatorial Optimization（IPCO），pp. 145-160，2002）的非线性设置，这表明，对于凸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 (International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145–160, 2002) 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 inO(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 factor), for quite general families of disjunctions. This is also complemented by examples where this gap is exponential (in the size of the input data).
登录
查看更多内容
混合整数优化中的分支定界和割平面的复杂性 — II
影响因子：
1.1
作者：
A. Basu;M. Conforti;M. D. Summa;Hongyi Jiang
通讯作者：
Hongyi Jiang
用于解决批量问题的分支定界树大小的下界
DOI：
10.1016/j.orl.2022.04.008
发表时间：
2021
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Santanu S. Dey;Prachi Shah
通讯作者：
Prachi Shah
DOI：
10.1287/moor.11.4.537
发表时间：
1986-11
期刊：
Math. Oper. Res.
影响因子：
--
作者：
M. Grötschel;W. Pulleyblank
通讯作者：
M. Grötschel;W. Pulleyblank
Chvátal 等级的界限
影响因子：
1.1
作者：
F. Eisenbrand;Andreas S. Schulz
通讯作者：
Andreas S. Schulz
论分支与剪切的威力和局限性
DOI：
10.4230/lipics.ccc.2021.6
发表时间：
2021
期刊：
Proceedings of the 36th Computational Complexity Conference
影响因子：
--
作者：
Noah Fleming;Mika Göös;R. Impagliazzo;T. Pitassi;Robert Robere;Li;A. Wigderson
通讯作者：
A. Wigderson