TY - JOUR

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

AU - Dey, Santanu S.

AU - Dubey, Yatharth

AU - Molinaro, Marco

N1 - Publisher Copyright:
© 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2023/3

Y1 - 2023/3

N2 - A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form π⊤x≤π0∨π⊤x≥π0+1, where π is an integer vector and π 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 Chvátal et al. (Linear Algebra Appl 114:455–499, 1989), who proved lower bounds for the Chvátal–Gomory rank.

AB - A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general disjunctions of the form π⊤x≤π0∨π⊤x≥π0+1, where π is an integer vector and π 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 Chvátal et al. (Linear Algebra Appl 114:455–499, 1989), who proved lower bounds for the Chvátal–Gomory rank.

UR - http://www.scopus.com/inward/record.url?scp=85124463785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85124463785&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01781-z

DO - 10.1007/s10107-022-01781-z

M3 - Article

AN - SCOPUS:85124463785

SN - 0025-5610

VL - 198

SP - 539

EP - 559

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -