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

A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general
disjunctions. 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 Chvatal et al., who proved lower bounds for the Chvatal-Gomory rank.