Computer Science Speaking Skills Talk

Wednesday, December 12, 2018 - 1:30pm to 2:30pm

Location:

7501 Gates Hillman Centers

Speaker:

ELLEN VITERCIK, Ph.D. Student http://www.cs.cmu.edu/~eviterci/

Learning to Branch


Speaker: Ellen Vitercik

Location: GHC 7501


Learning to Branch

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.

Based on joint work published in ICML 2018 with Nina Balcan, Travis Dick, and Tuomas Sandholm.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

For More Information, Contact:

Keywords:

Speaking Skills