Consider the problem Minimize: y Subject to: $2$x$1+2$x$2++2$x$15+$ y $<=15$ x$1,$ x$2,...,$ x$15,$ y in $\{0,1\}$ Show that the branch$-$and$-$bound method will always branch if seven or less variables have been branched on$.($In fact, most of the branches have almost all the variables set.$)$ This shows that branch$-$and$-$bound can take exponential time. For this problem, many solvers would catch what is happening in preprocessing and find the optimal solution almost immediately.