Machine learning augmented branch and bound for mixed integer linear programming

Area of Science:

• Mathematical Optimization
• Artificial Intelligence
• Computer Science

Background:

• Mixed Integer Linear Programming (MILP) is a crucial tool in optimization.
• The branch-and-bound algorithm is the primary method for solving MILPs.
• Traditional MILP solvers face challenges in efficiency for complex problems.

Purpose of the Study:

• To survey the integration of machine learning (ML) with MILP.
• To explore how ML enhances the branch-and-bound algorithm.
• To highlight ML's role in optimizing MILP solver performance.

Main Methods:

• Reviewing ML applications in primal heuristics, branching, cutting planes, node selection, and solver configuration.
• Analyzing ML algorithms for optimizing branch-and-bound efficiency metrics.
• Discussing MILP representations, benchmarks, and software for ML integration.

Main Results:

• Machine learning significantly boosts efficiency across various branch-and-bound tasks.
• ML enables automated optimization of solver performance.
• Integration of ML and mathematical optimization shows promising synergy.

Conclusions:

• ML is a transformative technology for MILP solving.
• The synergy between ML and mathematical optimization offers substantial benefits.
• Future research should focus on further integrating these complementary technologies.