論文の概要: Automatic Algorithm Selection for Pseudo-Boolean Optimization with Given
Computational Time Limits
- arxiv url: http://arxiv.org/abs/2309.03924v1
- Date: Thu, 7 Sep 2023 03:04:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-11 17:05:46.901792
- Title: Automatic Algorithm Selection for Pseudo-Boolean Optimization with Given
Computational Time Limits
- Title（参考訳）: 計算時間制限付き擬似ブール最適化の自動アルゴリズム選択
- Authors: Catalina Pezo and Dorit Hochbaum and Julio Godoy and Roberto Asin-Acha
- Abstract要約: 機械学習(ML)技術は、解決者のポートフォリオから最適な解法を自動選択するために提案されている。
これらのメソッドはメタソルバと呼ばれ、問題のインスタンスと解決者のポートフォリオを入力として取ります。
「Anytime」メタソルバは、指定された時間制限内で最高の性能の解決器を予測する。
- 参考スコア（独自算出の注目度）: 0.9831489366502301
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Machine learning (ML) techniques have been proposed to automatically select
the best solver from a portfolio of solvers, based on predicted performance.
These techniques have been applied to various problems, such as Boolean
Satisfiability, Traveling Salesperson, Graph Coloring, and others.
These methods, known as meta-solvers, take an instance of a problem and a
portfolio of solvers as input. They then predict the best-performing solver and
execute it to deliver a solution. Typically, the quality of the solution
improves with a longer computational time. This has led to the development of
anytime selectors, which consider both the instance and a user-prescribed
computational time limit. Anytime meta-solvers predict the best-performing
solver within the specified time limit.
Constructing an anytime meta-solver is considerably more challenging than
building a meta-solver without the "anytime" feature. In this study, we focus
on the task of designing anytime meta-solvers for the NP-hard optimization
problem of Pseudo-Boolean Optimization (PBO), which generalizes Satisfiability
and Maximum Satisfiability problems. The effectiveness of our approach is
demonstrated via extensive empirical study in which our anytime meta-solver
improves dramatically on the performance of Mixed Integer Programming solver
Gurobi, which is the best-performing single solver in the portfolio. For
example, out of all instances and time limits for which Gurobi failed to find
feasible solutions, our meta-solver identified feasible solutions for 47% of
these.
- Abstract（参考訳）: 予測性能に基づいて解法ポートフォリオから最適な解法を自動的に選択する機械学習(ml)手法が提案されている。
これらのテクニックは、Boolean Satisfiability、Traveing Salesperson、Graph Coloringなど、さまざまな問題に適用されている。
これらのメソッドはメタソルバと呼ばれ、問題のインスタンスと解決者のポートフォリオを入力として取ります。
そして、最高のパフォーマンスの解決方法を予測し、それを実行してソリューションを提供する。
典型的には、解の質は計算時間を長くすることで向上する。
これはインスタンスとユーザが指定した計算時間制限の両方を考慮し、任意の時間セレクタの開発につながった。
任意のメタ解決器は、指定された時間制限内で最高の性能の解決器を予測する。
anytimeメタソルバの構築は、"anytime"機能なしでメタソルバを構築するよりも、はるかに難しい。
本研究では, Pseudo-Boolean Optimization (PBO) のNPハード最適化問題に対して, 満足度と最大満足度を一般化したメタゾルバを設計する作業に焦点をあてる。
提案手法の有効性は,ポートフォリオにおける最高のシングルソルバであるMixed Integer Programming solver Gurobiのパフォーマンスにおいて,常にメタソルバが劇的に向上する,広範な実証研究によって実証された。
例えば、Gurobiが実現可能なソリューションを見つけられなかったすべてのインスタンスと時間制限の中で、私たちのメタソリューションは、これらの47%で実現可能なソリューションを特定しました。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem [2.9730678241643815]
教師付き機械学習に基づく予測解法選択手法を提案する。
70%以上の場合において、最良の解法が選択され、約90%の場合には、上位2の解法が選択される。
この探索は、量子ソルバ選択における機械学習の可能性を証明し、その自動化の基礎を定めている。
論文 参考訳（メタデータ） (2024-08-07T08:14:58Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳（メタデータ） (2023-07-18T04:29:16Z) - Socio-cognitive Optimization of Time-delay Control Problems using
Evolutionary Metaheuristics [89.24951036534168]
メタヒューリスティックス(Metaheuristics)は、古典的なアプローチでは解決できない難解な問題を解くために使用される普遍的な最適化アルゴリズムである。
本稿では,キャストに基づく新しい社会認知メタヒューリスティックの構築を目標とし,このアルゴリズムのいくつかのバージョンを時間遅延システムモデルの最適化に適用する。
論文 参考訳（メタデータ） (2022-10-23T22:21:10Z) - The Machine Learning for Combinatorial Optimization Competition (ML4CO):
Results and Insights [59.93939636422896]
ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。
このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
論文 参考訳（メタデータ） (2022-03-04T17:06:00Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。
本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。
可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
論文 参考訳（メタデータ） (2021-07-02T06:46:23Z) - Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。
正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。
最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
論文 参考訳（メタデータ） (2021-03-18T14:49:52Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-06-02T13:54:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。