Learning to Branch

Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik

ICML 2018 pp. 344-353

/icml/2018/balcan2018icml-learning/

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.

PDF ICML Semantic Scholar

Cite

Text

Balcan et al. "Learning to Branch." International Conference on Machine Learning, 2018.

Markdown

[Balcan et al. "Learning to Branch." International Conference on Machine Learning, 2018.](https://mlanthology.org/icml/2018/balcan2018icml-learning/)

BibTeX

@inproceedings{balcan2018icml-learning,
  title     = {{Learning to Branch}},
  author    = {Balcan, Maria-Florina and Dick, Travis and Sandholm, Tuomas and Vitercik, Ellen},
  booktitle = {International Conference on Machine Learning},
  year      = {2018},
  pages     = {344-353},
  volume    = {80},
  url       = {https://mlanthology.org/icml/2018/balcan2018icml-learning/}
}