Learning to Configure Separators in Branch-and-Cut
Sirui Li Wenbin Ouyang Max B. Paulus Cathy Wu
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.