  We study the complexity of cutting planes and branching schemes from a
theoretical point of view. We give some rigorous underpinnings to the
empirically observed phenomenon that combining cutting planes and branching
into a branch-and-cut framework can be orders of magnitude more efficient than
employing these tools on their own. In particular, we give general conditions
under which a cutting plane strategy and a branching scheme give a provably
exponential advantage in efficiency when combined into branch-and-cut. The
efficiency of these algorithms is evaluated using two concrete measures: number
of iterations and sparsity of constraints used in the intermediate
linear/convex programs. To the best of our knowledge, our results are the first
mathematically rigorous demonstration of the superiority of branch-and-cut over
pure cutting planes and pure branch-and-bound.
