論文の概要: Automatic MILP Solver Configuration By Learning Problem Similarities
- arxiv url: http://arxiv.org/abs/2307.00670v1
- Date: Sun, 2 Jul 2023 21:31:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 14:46:06.731697
- Title: Automatic MILP Solver Configuration By Learning Problem Similarities
- Title(参考訳): 問題類似性学習によるMILPソルバーの自動構成
- Authors: Abdelrahman Hosny, Sherief Reda
- Abstract要約: 混合線形プログラム(MILP)は、内部アルゴリズムを制御するために多数の構成パラメータを公開する。
我々は,探索・評価設定のオーバーヘッドを伴わずに,低コストなソリューションを実現する未確認問題インスタンスの構成パラメータを予測することを目的としている。
1つのソルバ構成で同様のコストを持つインスタンスも、同じランタイム環境で別のソルバ構成で同様のコストを持つことを示す。
- 参考スコア(独自算出の注目度): 1.1585113506994469
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A large number of real-world optimization problems can be formulated as Mixed
Integer Linear Programs (MILP). MILP solvers expose numerous configuration
parameters to control their internal algorithms. Solutions, and their
associated costs or runtimes, are significantly affected by the choice of the
configuration parameters, even when problem instances have the same number of
decision variables and constraints. On one hand, using the default solver
configuration leads to suboptimal solutions. On the other hand, searching and
evaluating a large number of configurations for every problem instance is
time-consuming and, in some cases, infeasible. In this study, we aim to predict
configuration parameters for unseen problem instances that yield lower-cost
solutions without the time overhead of searching-and-evaluating configurations
at the solving time. Toward that goal, we first investigate the cost
correlation of MILP problem instances that come from the same distribution when
solved using different configurations. We show that instances that have similar
costs using one solver configuration also have similar costs using another
solver configuration in the same runtime environment. After that, we present a
methodology based on Deep Metric Learning to learn MILP similarities that
correlate with their final solutions' costs. At inference time, given a new
problem instance, it is first projected into the learned metric space using the
trained model, and configuration parameters are instantly predicted using
previously-explored configurations from the nearest neighbor instance in the
learned embedding space. Empirical results on real-world problem benchmarks
show that our method predicts configuration parameters that improve solutions'
costs by up to 38% compared to existing approaches.
- Abstract(参考訳): 多くの実世界の最適化問題をMILP(Mixed Integer Linear Programs)として定式化することができる。
MILPソルバは内部アルゴリズムを制御するために多数の設定パラメータを公開する。
問題インスタンスが同じ数の決定変数と制約を持つ場合でも、ソリューションとその関連するコストやランタイムは、設定パラメータの選択によって大きく影響を受ける。
一方、デフォルトのソルバ構成を使用することで、最適化されたソリューションが実現される。
一方で、問題インスタンス毎の多数の構成の検索と評価には時間がかかり、場合によっては実現不可能な場合もある。
本研究では,探索・評価設定の時間的オーバーヘッドを伴わずに,低コストなソリューションを実現する未確認問題インスタンスの構成パラメータを予測することを目的とする。
その目的に向けて,我々はまず,異なる構成を用いて解くと,同一分布から生じるmilp問題インスタンスのコスト相関について検討する。
同様のコストを持つインスタンスが,同じランタイム環境において,別のソルバ構成を使用する場合も同様のコストを持つことを示す。
その後、最終ソリューションのコストと相関するMILP類似性を学習するためのDeep Metric Learningに基づく方法論を提案する。
新しい問題インスタンスが与えられた場合、まずトレーニングされたモデルを用いて学習されたメトリック空間に投影し、学習された埋め込み空間内の隣のインスタンスから探索された設定を用いて構成パラメータを即座に予測する。
実世界の問題ベンチマーク実験の結果,提案手法は既存手法と比較して最大38%のコスト削減を実現する構成パラメータを予測できることがわかった。
関連論文リスト
Err
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。