Machine learning augmented branch and bound for mixed integer linear programming

• 成果类型: Article; Early Access
• 署名作者: Scavuzzo, Lara; Aardal, Karen; Lodi, Andrea; Yorke-Smith, Neil
• 署名单位: Delft University of Technology; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02130-y
• 发表日期: 2024
• 关键词: gomory cuts; approximation; FRAMEWORK; algorithm; backdoors; IMPACT; rules

摘要

Mixed Integer Linear Programming (MILP) is a pillar of mathematical optimization that offers a powerful modeling language for a wide range of applications. The main engine for solving MILPs is the branch-and-bound algorithm. Adding to the enormous algorithmic progress in MILP solving of the past decades, in more recent years there has been an explosive development in the use of machine learning for enhancing all main tasks involved in the branch-and-bound algorithm. These include primal heuristics, branching, cutting planes, node selection and solver configuration decisions. This article 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 appropriate MILP representations, benchmarks and software tools used in the context of applying learning algorithms.