論文の概要: Neur2RO: Neural Two-Stage Robust Optimization
- arxiv url: http://arxiv.org/abs/2310.04345v2
- Date: Fri, 15 Mar 2024 14:51:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 03:02:24.798911
- Title: Neur2RO: Neural Two-Stage Robust Optimization
- Title（参考訳）: Neur2RO: ニューラルネットワークによる2段階ロバスト最適化
- Authors: Justin Dumouchelle, Esther Julien, Jannis Kurtz, Elias B. Khalil,
- Abstract要約: カラム・アンド・制約生成(CCG)の効率的な機械学習によるインスタンス化であるNeur2ROを提案する。
我々は、設計によって簡単に最適化できる新しいニューラルネットワークアーキテクチャにより、第二段階の問題の価値関数を推定することを学ぶ。
資本予算の面では、Neur2ROは$k$-adaptabilityアルゴリズムの3つの変種、特に最大のインスタンスにおいて、ソリューション時間の10倍から100倍の削減を達成している。
- 参考スコア（独自算出の注目度）: 15.876446950057389
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Robust optimization provides a mathematical framework for modeling and solving decision-making problems under worst-case uncertainty. This work addresses two-stage robust optimization (2RO) problems (also called adjustable robust optimization), wherein first-stage and second-stage decisions are made before and after uncertainty is realized, respectively. This results in a nested min-max-min optimization problem which is extremely challenging computationally, especially when the decisions are discrete. We propose Neur2RO, an efficient machine learning-driven instantiation of column-and-constraint generation (CCG), a classical iterative algorithm for 2RO. Specifically, we learn to estimate the value function of the second-stage problem via a novel neural network architecture that is easy to optimize over by design. Embedding our neural network into CCG yields high-quality solutions quickly as evidenced by experiments on two 2RO benchmarks, knapsack and capital budgeting. For knapsack, Neur2RO finds solutions that are within roughly $2\%$ of the best-known values in a few seconds compared to the three hours of the state-of-the-art exact branch-and-price algorithm; for larger and more complex instances, Neur2RO finds even better solutions. For capital budgeting, Neur2RO outperforms three variants of the $k$-adaptability algorithm, particularly on the largest instances, with a 10 to 100-fold reduction in solution time. Our code and data are available at https://github.com/khalil-research/Neur2RO.
- Abstract（参考訳）: ロバスト最適化は、最悪の不確実性の下で意思決定問題をモデル化し、解決するための数学的フレームワークを提供する。
この研究は、2段階のロバスト最適化 (2RO) 問題(調整可能なロバスト最適化とも呼ばれる)に対処する。
これは、特に決定が離散的である場合、計算的に非常に難しいネストされた min-max-min 最適化問題をもたらす。
我々は,2ROの古典的反復アルゴリズムである,カラム・アンド・制約生成(CCG)の効率的な機械学習によるインスタンス化であるNeur2ROを提案する。
具体的には、設計によって簡単に最適化できる新しいニューラルネットワークアーキテクチャを用いて、第2段階の問題の価値関数を推定することを学ぶ。
ニューラルネットワークをCCGに組み込むと、クナップサックと資本予算という2つの2ROベンチマークの実験によって証明されたような、高品質なソリューションがすぐに得られます。
knapsackの場合、Neur2ROは最先端の正確なブランチ・アンド・プライスアルゴリズムの3時間と比較すると、数秒で最もよく知られた値の約2.%以内のソリューションを見つける。
資本予算の面では、Neur2ROは$k$-adaptabilityアルゴリズムの3つの変種、特に最大のインスタンスにおいて、ソリューション時間の10倍から100倍の削減を達成している。
私たちのコードとデータはhttps://github.com/khalil-research/Neur2ROで公開されています。
関連論文リスト
- Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
制約付き最適化のための学習型反復解法を提案する。
解法を特定のパラメトリック最適化問題にカスタマイズすることで、非常に高速で正確な解を得ることができる。
最適性のKarush-Kuhn-Tucker条件に基づく新しい損失関数を導入し、両ニューラルネットワークの完全な自己教師付きトレーニングを可能にする。
論文 参考訳（メタデータ） (2024-09-12T14:17:23Z) - RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。
我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
論文 参考訳（メタデータ） (2023-11-10T13:56:15Z) - A Machine Learning Approach to Two-Stage Adaptive Robust Optimization [6.943816076962257]
本稿では,2段階線形適応ロバスト最適化問題の解法として,機械学習に基づくアプローチを提案する。
私たちは、最適な今と現在の決定、最適な今と現在の決定に関連する最悪のシナリオ、そして最適な待ちと見る決定をエンコードします。
私たちは、現在と現在の決定のための高品質な戦略、最適な今と現在の決定に関連する最悪のシナリオ、待機と見る決定を予測できる機械学習モデルをトレーニングします。
論文 参考訳（メタデータ） (2023-07-23T19:23:06Z) - Learning To Dive In Branch And Bound [95.13209326119153]
グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。
我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
論文 参考訳（メタデータ） (2023-01-24T12:01:45Z) - Neur2SP: Neural Two-Stage Stochastic Programming [3.5417030119735045]
我々はニューラルネットワークを介して期待値関数を近似する新しい方法Neur2SPを開発した。
Neur2SPはすべての問題に対して1.66秒未満で、シナリオの数が増えても高品質なソリューションを実現する。
論文 参考訳（メタデータ） (2022-05-20T22:09:22Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。
このアプローチは多くの実装と最適化の課題をもたらします。
提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文 参考訳（メタデータ） (2021-03-18T14:26:26Z) - Slowly Varying Regression under Sparsity [5.22980614912553]
本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。
本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。
結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-02-22T04:51:44Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳（メタデータ） (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。