2023-12-05 マサチューセッツ工科大学(MIT)
◆この新しい手法は、MILPソルバーの処理速度を30～70％向上させ、精度に影響を与えませんでした。企業はこの手法を使用して、最適な解を迅速に得るか、特に複雑な問題に対しては実行可能な時間内でより良い解を得ることができます。この手法は、ライドシェアサービス、電力網オペレータ、ワクチンディストリビュータなど、資源割り当ての難しい問題に直面するあらゆるエンティティで利用可能です。
＜関連情報＞
- https://news.mit.edu/2023/ai-accelerates-problem-solving-complex-scenarios-1205
- https://arxiv.org/abs/2311.05650
ブランチ・アンド・カットでセパレーターの構成を学ぶ Learning to Configure Separators in Branch-and-Cut
Sirui Li, Wenbin Ouyang, Max B. Paulus, Cathy Wu
arXiv Submitted on 8 Nov 2023
DOI:https://doi.org/10.48550/arXiv.2311.05650
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.
Abstract
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.
