Learning to Branch

Understand

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.