論文の概要: There is No Silver Bullet: Benchmarking Methods in Predictive Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2311.07633v3
- Date: Tue, 13 Aug 2024 10:43:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 23:14:44.122275
- Title: There is No Silver Bullet: Benchmarking Methods in Predictive Combinatorial Optimization
- Title(参考訳): 銀の弾丸は存在しない:予測的コンビニティブ最適化におけるベンチマーク手法
- Authors: Haoyu Geng, Hang Ruan, Runzhong Wang, Yang Li, Yang Wang, Lei Chen, Junchi Yan,
- Abstract要約: 予測最適化(英: Predictive optimization)は、エネルギーコストを意識したスケジューリングや広告予算配分など、多くの現実世界のアプリケーションの正確なモデリングである。
モジュールレベルでの設計選択を含む、両方のアプローチのシステマティックなベンチマークはありません。
本研究は,8ベンチマーク中7ベンチマークにおいて,PnOアプローチがPtOよりも優れていることを示すが,PnOの設計選択に銀の弾丸は見つからない。
- 参考スコア(独自算出の注目度): 59.27851754647913
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Predictive combinatorial optimization, where the parameters of combinatorial optimization (CO) are unknown at the decision-making time, is the precise modeling of many real-world applications, including energy cost-aware scheduling and budget allocation on advertising. Tackling such a problem usually involves a prediction model and a CO solver. These two modules are integrated into the predictive CO pipeline following two design principles: ``Predict-then-Optimize (PtO)'', which learns predictions by supervised training and subsequently solves CO using predicted coefficients, while the other, named ``Predict-and-Optimize (PnO)'', directly optimizes towards the ultimate decision quality and claims to yield better decisions than traditional PtO approaches. However, there lacks a systematic benchmark of both approaches, including the specific design choices at the module level, as well as an evaluation dataset that covers representative real-world scenarios. To this end, we develop a modular framework to benchmark 11 existing PtO/PnO methods on 8 problems, including a new industrial dataset for combinatorial advertising that will be released. Our study shows that PnO approaches are better than PtO on 7 out of 8 benchmarks, but there is no silver bullet found for the specific design choices of PnO. A comprehensive categorization of current approaches and integration of typical scenarios are provided under a unified benchmark. Therefore, this paper could serve as a comprehensive benchmark for future PnO approach development and also offer fast prototyping for application-focused development.
- Abstract(参考訳): 予測的組合せ最適化(英: Predictive combinatorial optimization、CO)とは、エネルギーコストを意識したスケジューリングや広告予算の割り当てなど、現実の多くのアプリケーションの正確なモデリングである。
このような問題に対処するには、通常予測モデルとCOソルバが関係する。
これら2つのモジュールは,2つの設計原則に従って予測COパイプラインに統合される: ‘予測最適化(PtO)’; 教師付きトレーニングによって予測を学習し,その後予測係数を用いてCOを解く。
しかしながら、モジュールレベルでの設計選択を含む、両方のアプローチのシステマティックなベンチマークや、代表的な実世界のシナリオをカバーする評価データセットが欠落している。
そこで本研究では,既存のPtO/PnOメソッド11を8つの問題に対してベンチマークするモジュラーフレームワークを開発した。
本研究は,8ベンチマーク中7ベンチマークにおいて,PnOアプローチがPtOよりも優れていることを示すが,PnOの設計選択に銀の弾丸は見つからない。
現在のアプローチの包括的な分類と典型的なシナリオの統合は、統一されたベンチマークの下で提供される。
したがって,本論文は今後のPnOアプローチ開発のための包括的なベンチマークとして機能し,アプリケーション中心の開発に高速なプロトタイピングを提供する。
関連論文リスト
- Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
最近の構造化学習手法のストリームは、様々な最適化問題に対する技術の実践的状態を改善している。
鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。
本稿では,最適化を容易にし,一般化誤差を改善するポリシを摂動することでリスクを円滑にする手法について検討する。
論文 参考訳(メタデータ) (2024-07-24T12:00:30Z) - Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization [6.713974813995327]
本稿では、メモリを活用するRLアプローチであるMementOについて述べる。
本稿では,特にTraveing SalesmanとCapacitated Vehicle Routingのベンチマーク問題に対する有効性を検証する。
論文 参考訳(メタデータ) (2024-06-24T08:18:19Z) - An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
効率的な確率的選択に基づく制約付き多目的EAをPSCMOEAと呼ぶ。
a) 評価された解の実現可能性と収束状態に基づく適応探索境界同定スキームのような新しい要素を含む。
ECMOPを模擬する低評価予算を用いて, 幅広い制約付き問題に対して, 数値実験を行った。
論文 参考訳(メタデータ) (2024-05-22T02:32:58Z) - Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。
学習シナリオにおける同値性に基づく単一のフレームワークを提案する。
我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
論文 参考訳(メタデータ) (2024-05-09T12:52:22Z) - End-to-End Learning for Fair Multiobjective Optimization Under
Uncertainty [55.04219793298687]
機械学習における予測-Then-Forecast(PtO)パラダイムは、下流の意思決定品質を最大化することを目的としている。
本稿では,PtO法を拡張して,OWA(Nondifferentiable Ordered Weighted Averaging)の目的を最適化する。
この結果から,不確実性の下でのOWA関数の最適化とパラメトリック予測を効果的に統合できることが示唆された。
論文 参考訳(メタデータ) (2024-02-12T16:33:35Z) - Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and
Optimization [59.386153202037086]
Predict-Then-フレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
このアプローチは非効率であり、最適化ステップを通じてバックプロパゲーションのための手作りの、問題固有のルールを必要とする。
本稿では,予測モデルを用いて観測可能な特徴から最適解を直接学習する手法を提案する。
論文 参考訳(メタデータ) (2023-11-22T01:32:06Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳(メタデータ) (2023-01-28T01:50:42Z) - Uncertainty-Aware Search Framework for Multi-Objective Bayesian
Optimization [40.40632890861706]
高価な関数評価を用いたマルチオブジェクト(MO)ブラックボックス最適化の問題点を考察する。
UeMOと呼ばれる新しい不確実性対応検索フレームワークを提案し、評価のための入力シーケンスを効率的に選択する。
論文 参考訳(メタデータ) (2022-04-12T16:50:48Z) - Optimistic variants of single-objective bilevel optimization for
evolutionary algorithms [6.788217433800101]
ベンチマーク問題を解くために部分的部分進化的アプローチが提案され、優れた結果が得られた。
また、一般的な収束アプローチ、すなわち楽観的で悲観的なアプローチにも新しい変種が提案されている。
実験の結果、アルゴリズムは楽観的な変量を持つ最適解に異なる収束性を示す。
論文 参考訳(メタデータ) (2020-08-22T23:12:07Z) - Benchmarking for Metaheuristic Black-Box Optimization: Perspectives and
Open Challenges [0.0]
新たな最適化アルゴリズムの研究は、そのようなアルゴリズムが現実世界や産業に関係のある課題に対処する能力を改善するという動機に基づいていることが多い。
多くのテスト問題とベンチマークスイートが開発され、アルゴリズムの比較評価に利用されている。
論文 参考訳(メタデータ) (2020-07-01T15:09:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。