Learning to Configure Separators in Branch-and-Cut
This work addresses the challenge of optimizing separator management in MILP solvers, which is incremental as it builds on prior learning-based methods for cutting plane selection.
The paper tackles the problem of accelerating mixed integer linear program (MILP) solvers by learning to select and configure separators for cutting planes, resulting in up to 72% and 37% improvements in solve time on synthetic and real-world benchmarks.
Cutting planes are crucial in solving mixed integer linear programs (MILP) as they facilitate bound improvements on the optimal solution. Modern MILP solvers rely on a variety of separators to generate a diverse set of cutting planes by invoking the separators frequently during the solving process. This work identifies that MILP solvers can be drastically accelerated by appropriately selecting separators to activate. As the combinatorial separator selection space imposes challenges for machine learning, we learn to separate by proposing a novel data-driven strategy to restrict the selection space and a learning-guided algorithm on the restricted space. Our method predicts instance-aware separator configurations which can dynamically adapt during the solve, effectively accelerating the open source MILP solver SCIP by improving the relative solve time up to 72% and 37% on synthetic and real-world MILP benchmarks. Our work complements recent work on learning to select cutting planes and highlights the importance of separator management.