Learning to Branch

Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:344-353, 2018.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-balcan18a, title = {Learning to Branch}, author = {Balcan, Maria-Florina and Dick, Travis and Sandholm, Tuomas and Vitercik, Ellen}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {344--353}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/balcan18a/balcan18a.pdf}, url = {https://proceedings.mlr.press/v80/balcan18a.html}, 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.} }
Endnote
%0 Conference Paper %T Learning to Branch %A Maria-Florina Balcan %A Travis Dick %A Tuomas Sandholm %A Ellen Vitercik %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-balcan18a %I PMLR %P 344--353 %U https://proceedings.mlr.press/v80/balcan18a.html %V 80 %X 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.
APA
Balcan, M., Dick, T., Sandholm, T. & Vitercik, E.. (2018). Learning to Branch. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:344-353 Available from https://proceedings.mlr.press/v80/balcan18a.html.

Related Material