Learning to Run Heuristics in Tree Search

By Elias Boutros Khalil, Bistra N. Dilkina, George L. Nemhauser, Shabbir Ahmed, Yufen Shao. 2017

155 citations recorded by the source corpus.

“Primal heuristics” are a key contributor to the improved performance of exact branch-and-bound solvers for combinatorial optimization and integer programming. Perhaps the most crucial question concerning primal heuristics is that of at which nodes they should run, to which the typical answer is via hard-coded rules or fixed solver parameters tuned, offline, by trial-and-error. Alternatively, a heuristic should be run when it is most likely to succeed, based on the problem instance’s characteristics, the state of the search, etc. In this work, we study the problem of deciding at which node a heuristic should be run, such that the overall (primal) performance of the solver is optimized. To our knowledge, this is the first attempt at formalizing and systematically addressing this problem. Central to our approach is the use of Machine Learning (ML) for predicting whether a heuristic will succeed at a given node. We give a theoretical framework for analyzing this decision-making process in a simplified setting, propose a ML approach for modeling heuristic success likelihood, and design practical rules that leverage the ML models to dynamically decide whether to run a heuristic at each node of the search tree. Experimentally, our approach improves the primal performance of a stateof-the-art Mixed Integer Programming solver by up to 6% on a set of benchmark instances, and by up to 60% on a family of hard Independent Set instances.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Industrial and Manufacturing Engineering, Reinforcement Learning, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

In Reinforcement Learning

In Algorithms & Complexity

Citations in the corpus

Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “This thread includes machine learning methods for branching [26, 22], tree node selection [16, 34], and heuristic selection [35, 23].”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, methodology): “…of the oracle procedure that expands the node whose feasible set contains the optimal solution, while Song et al. [48] learn node selection and pruning heuristics by imitation learning of shortest paths to good feasible solutions, and Khalil et al. [32] learn primal heuristics for B&B algorithms.”
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon (2018, background): “Khalil et al. (2017b) build an ML model to predict whether or not running a given heuristic will yield a better solution than the best one found so far and then greedily run that heuristic whenever the outcome of the model is positive.”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “Khalil et al. (2017b) learn a binary classifier offline to predict whether applying a primal heuristic at a branch-and-bound node will succeed in finding an incumbent.”