Lower bounds on the size of general branch-and-bound trees

• 成果类型: Article
• 署名作者: Dey, Santanu S.; Dubey, Yatharth; Molinaro, Marco
• 署名单位: University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01781-z
• 发表日期: 2023
• 页码: 539-559
• 关键词: cutting-plane proofs; basis reduction; split

摘要

A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form pi(T) x <= pi(0) V pi(T) x >= pi(0) + 1, where pi is an integer vector and pi(0) is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the size of general branch-and-bound trees persists even when we add Gaussian noise to the coefficients of the cross-polytope, thus showing that a polynomial-size smoothed analysis upper bound is not possible. The results in this paper can be viewed as the branch-and-bound analog of the seminal paper by Chvatal et al. (Linear Algebra Appl 114:455-499, 1989), who proved lower bounds for the Chvatal-Gomory rank.