Machine Learning Augmented Branch and Bound for Mixed Integer Linear
  Programming
Lara Scavuzzo Karen Aardal Andrea Lodi Neil Yorke-Smith
Mixed Integer Linear Programming (MILP) is a pillar of mathematical
optimization that offers a powerful modeling language for a wide range of
applications. During the past decades, enormous algorithmic progress has been
made in solving MILPs, and many commercial and academic software packages
exist. Nevertheless, the availability of data, both from problem instances and
from solvers, and the desire to solve new problems and larger (real-life)
instances, trigger the need for continuing algorithmic development. MILP
solvers use branch and bound as their main component. In recent years, there
has been an explosive development in the use of machine learning algorithms for
enhancing all main tasks involved in the branch-and-bound algorithm, such as
primal heuristics, branching, cutting planes, node selection and solver
configuration decisions. This paper presents a survey of such approaches,
addressing the vision of integration of machine learning and mathematical
optimization as complementary technologies, and how this integration can
benefit MILP solving. In particular, we give detailed attention to machine
learning algorithms that automatically optimize some metric of branch-and-bound
efficiency. We also address how to represent MILPs in the context of applying
learning algorithms, MILP benchmarks and software.