Complexity of branch-and-bound and cutting planes in mixed-integer optimization

• 成果类型: Article
• 署名作者: Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Jiang, Hongyi
• 署名单位: Johns Hopkins University; University of Padua
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01789-5
• 发表日期: 2023
• 页码: 787-810
• 关键词: traveling salesman problem; nonsymmetric convex-bodies; chvatal rank; proofs; polytopes; inequalities; graphs; cuts

摘要

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 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 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).