  A \emph{general branch-and-bound tree} is a branch-and-bound tree which is
allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0
\,\vee\, \pi^{\top}x \geq \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 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\'atal et al.
\cite{chvatal1989cutting}, who proved lower bounds for the Chv\'atal-Gomory
rank.
