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

ad

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

◆MITとETH Zurichの研究者は、混合整数線形計画(MILP)ソルバーの最適化問題を解決するために、機械学習を使用しました。従来の手法の中間ステップを簡略化するフィルタリング技術を導入し、機械学習を活用して特定の問題に対する最適な解を見つけました。
◆この新しい手法は、MILPソルバーの処理速度を30~70%向上させ、精度に影響を与えませんでした。企業はこの手法を使用して、最適な解を迅速に得るか、特に複雑な問題に対しては実行可能な時間内でより良い解を得ることができます。この手法は、ライドシェアサービス、電力網オペレータ、ワクチンディストリビュータなど、資源割り当ての難しい問題に直面するあらゆるエンティティで利用可能です。

<関連情報>

ブランチ・アンド・カットでセパレーターの構成を学ぶ 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

AIが複雑なシナリオでの問題解決を加速する(AI accelerates problem-solving in complex scenarios)
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.

1504数理・情報
ad
ad
Follow
ad
タイトルとURLをコピーしました