Skip to yearly menu bar Skip to main content


Poster

Learning to Branch

Nina Balcan · Travis Dick · Tuomas Sandholm · Ellen Vitercik

Hall B #144

Abstract:

Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial problems. These algorithms recursively partition the search space to find an optimal solution. To keep the tree small, it is crucial to carefully decide, when expanding a tree node, which variable to branch on at that node to partition the remaining space. Many partitioning techniques have been proposed, but no theory describes which 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. Via theory and experiments, we show that learning to branch is both practical and hugely beneficial.

Live content is unavailable. Log in and register to view live content