Lower Bounds on the Size of General Branch-and-Bound Trees
share
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 π_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 when we add Gaussian noise to the coefficients of the cross polytope, thus showing that 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. <cit.>, who proved lower bounds for the Chvátal-Gomory rank.
READ FULL TEXT