  Tree search algorithms, such as branch-and-bound, are the most widely used
tools for solving combinatorial and nonconvex problems. For example, they are
the foremost method for solving (mixed) integer programs and constraint
satisfaction problems. Tree search algorithms recursively partition the search
space to find an optimal solution. In order to keep the tree size small, it is
crucial to carefully decide, when expanding a tree node, which question
(typically variable) to branch on at that node in order to partition the
remaining space. Numerous partitioning techniques (e.g., variable selection)
have been proposed, but there is no theory describing which technique is
optimal. We show how to use machine learning to determine an optimal weighting
of any set of partitioning procedures for the instance distribution at hand
using samples from the distribution. We provide the first sample complexity
guarantees for tree search algorithm configuration. These guarantees bound the
number of samples sufficient to ensure that the empirical performance of an
algorithm over the samples nearly matches its expected performance on the
unknown instance distribution. This thorough theoretical investigation
naturally gives rise to our learning algorithm. Via experiments, we show that
learning an optimal weighting of partitioning procedures can dramatically
reduce tree size, and we prove that this reduction can even be exponential.
Through theory and experiments, we show that learning to branch is both
practical and hugely beneficial.
