Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming

Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming

8 Feb 2024 | Lara Scavuzzo, Karen Aardal, Andrea Lodi, Neil Yorke-Smith
This paper surveys the integration of machine learning (ML) with branch and bound (B&B) algorithms in Mixed Integer Linear Programming (MILP) solvers. It highlights the need for algorithmic advancements to solve larger and more complex MILP instances, driven by the availability of data and the desire to explore new application domains. The paper focuses on how ML can enhance key components of the B&B algorithm, such as primal heuristics, branching, cutting planes, node selection, and solver configuration decisions. It emphasizes the use of ML to automatically optimize metrics of B&B efficiency, rather than relying on heuristics that are time-consuming but effective. The survey covers various ML techniques, including supervised learning and reinforcement learning, and discusses their application in MILP solving. It also addresses the representation of MILPs, benchmark datasets, and software tools used in the literature. The paper aims to provide a comprehensive overview of the current state of ML-augmented B&B in MILP, highlighting both the potential benefits and the challenges in generalizing these methods to a wider range of problem instances.This paper surveys the integration of machine learning (ML) with branch and bound (B&B) algorithms in Mixed Integer Linear Programming (MILP) solvers. It highlights the need for algorithmic advancements to solve larger and more complex MILP instances, driven by the availability of data and the desire to explore new application domains. The paper focuses on how ML can enhance key components of the B&B algorithm, such as primal heuristics, branching, cutting planes, node selection, and solver configuration decisions. It emphasizes the use of ML to automatically optimize metrics of B&B efficiency, rather than relying on heuristics that are time-consuming but effective. The survey covers various ML techniques, including supervised learning and reinforcement learning, and discusses their application in MILP solving. It also addresses the representation of MILPs, benchmark datasets, and software tools used in the literature. The paper aims to provide a comprehensive overview of the current state of ML-augmented B&B in MILP, highlighting both the potential benefits and the challenges in generalizing these methods to a wider range of problem instances.
Reach us at info@study.space
[slides and audio] Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming