論文の概要: 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%のコスト削減を実現する構成パラメータを予測できることがわかった。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows [0.0]
本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。
その類似度基準は、顧客の空間的、時間的、需要データを含む。
本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
論文 参考訳（メタデータ） (2024-01-20T06:06:01Z) - Learning to Configure Mathematical Programming Solvers by Mathematical
Programming [0.8075866265341176]
本稿では,与えられた問題の特定の事例に対して,優れた数学的プログラミング解法構成を求める問題について論じる。
優れたソルバ構成を学ぶことの難しさは、パラメータ設定がすべて独立しているとは限らないことである。
このアプローチの第2段階でこの問題に対処し、学習した情報を用いて最適化問題を構築し、解決する。
論文 参考訳（メタデータ） (2024-01-10T10:02:01Z) - A learning-based mathematical programming formulation for the automatic
configuration of optimization solvers [0.8075866265341176]
我々は、解決者の性能関数を学習するために、解決されたインスタンスと構成のセットを用いる。
対象/制約が学習情報を明示的に符号化する混合整数非線形プログラムを定式化する。
論文 参考訳（メタデータ） (2024-01-08T21:10:56Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳（メタデータ） (2023-04-01T15:50:18Z) - The Machine Learning for Combinatorial Optimization Competition (ML4CO):
Results and Insights [59.93939636422896]
ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。
このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
論文 参考訳（メタデータ） (2022-03-04T17:06:00Z) - Learning Hard Optimization Problems: A Data Generation Perspective [44.4747903763245]
本稿では,トレーニングデータのボラティリティと,それを近似する能力について述べる。
そこで本研究では,教師付きタスクに対処可能な最適化問題に対して,(実際にあるいは近似的に)解を生成(生成)する方法を提案する。
論文 参考訳（メタデータ） (2021-06-04T17:03:44Z) - Memory Clustering using Persistent Homology for Multimodality- and
Discontinuity-Sensitive Learning of Optimal Control Warm-starts [24.576214898129823]
シューティング法は非線形最適制御問題の解法として効率的である。
最近の研究は、問題空間のオフライン探索中に生成されたサンプルに基づいてトレーニングされた学習モデルからの最初の推測を提供することに重点を置いている。
本研究では、代数的トポロジーからツールを適用し、解空間の基盤構造に関する情報を抽出する。
論文 参考訳（メタデータ） (2020-10-02T14:24:59Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。