AIが複雑なシナリオでの問題解決を加速する(AI accelerates problem-solving in complex scenarios)


2023-12-05 マサチューセッツ工科大学(MIT)

◆MITとETH Zurichの研究者は、混合整数線形計画(MILP)ソルバーの最適化問題を解決するために、機械学習を使用しました。従来の手法の中間ステップを簡略化するフィルタリング技術を導入し、機械学習を活用して特定の問題に対する最適な解を見つけました。


ブランチ・アンド・カットでセパレーターの構成を学ぶ Learning to Configure Separators in Branch-and-Cut

Sirui Li, Wenbin Ouyang, Max B. Paulus, Cathy Wu
arXiv  Submitted on 8 Nov 2023

Figure 1: Separator Configuration in Branch-and-Cut (B&C). Modern MILP solvers perform
Branch-and-Bound (B&B) tree search to solve MILPs. At each node of the B&B tree, cuts are added
to tighten the Linear Programming (LP) relaxation of the MILP.


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.