論文の概要: Neur2RO: Neural Two-Stage Robust Optimization
- arxiv url: http://arxiv.org/abs/2310.04345v1
- Date: Fri, 6 Oct 2023 16:11:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-09 15:07:25.198007
- Title: Neur2RO: Neural Two-Stage Robust Optimization
- Title(参考訳): Neur2RO: ニューラルネットワークによる2段階ロバスト最適化
- Authors: Justin Dumouchelle, Esther Julien, Jannis Kurtz, Elias B. Khalil
- Abstract要約: この研究は、2段階のロバスト最適化(2RO)問題に対処し、第1段階と第2段階の決定を不確かさの前後に行う。
我々は,コラム・アンド・制約生成(CCG)の効率的な機械学習によるインスタンス化であるNeur2ROを提案する。
我々は、設計によって簡単に最適化できる新しいニューラルネットワークアーキテクチャにより、第二段階の問題の価値関数を推定することを学ぶ。
- 参考スコア(独自算出の注目度): 17.34387773676538
- 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 5 to 10-fold reduction in solution time. Our code
and data are available at https://github.com/khalil-research/Neur2RO.
- Abstract(参考訳): ロバスト最適化は、最悪の不確実性の下で意思決定問題をモデル化および解決するための数学的フレームワークを提供する。
本研究は、2段階のロバスト最適化(2ro)問題(調整可能なロバスト最適化とも呼ばれる)に対処し、1段階目と2段階目はそれぞれ不確実性の実現前後で決定される。
これは、特に決定が離散的である場合、計算的に非常に難しいネストされた min-max-min 最適化問題をもたらす。
我々は,2ROの古典的反復アルゴリズムである,カラム・アンド・制約生成(CCG)の効率的な機械学習によるインスタンス化であるNeur2ROを提案する。
具体的には,設計によって最適化が容易な新たなニューラルネットワークアーキテクチャを用いて,第2段階問題の価値関数を推定することを学ぶ。
ニューラルネットワークをCCGに組み込むと、クナップサックと資本予算という2つの2ROベンチマークの実験によって証明されたような、高品質なソリューションがすぐに得られます。
knapsackの場合、Neur2ROは最先端の正確なブランチ・アンド・プライスアルゴリズムの3時間と比較すると、数秒で最もよく知られた値の約2.%以内のソリューションを見つける。
資本予算の面では、neur2roはk$-adaptabilityアルゴリズムの3つの変種、特に最大インスタンスにおいて、ソリューション時間の5倍から10倍削減されている。
私たちのコードとデータはhttps://github.com/khalil-research/neur2roで入手できます。
関連論文リスト
- A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
汎用的な純粋量子近似最適化アルゴリズムを提案する。
このアルゴリズムは$p$レベルの分割・対数構造に構成されている。
2つの最適化問題の必要なキュービット数が10である場合、アルゴリズムの性能を詳細に示す。
論文 参考訳(メタデータ) (2023-10-27T06:54:39Z) - A Machine Learning Approach to Two-Stage Adaptive Robust Optimization [6.943816076962257]
本稿では,2段階線形適応ロバスト最適化問題の解法として,機械学習に基づくアプローチを提案する。
私たちは、最適な今と現在の決定、最適な今と現在の決定に関連する最悪のシナリオ、そして最適な待ちと見る決定をエンコードします。
私たちは、現在と現在の決定のための高品質な戦略、最適な今と現在の決定に関連する最悪のシナリオ、待機と見る決定を予測できる機械学習モデルをトレーニングします。
論文 参考訳(メタデータ) (2023-07-23T19:23:06Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T04:57:37Z) - Machine Learning for $K$-adaptability in Two-stage Robust Optimization [1.2891210250935143]
2段階の頑健な最適化問題は、最も難しい最適化問題の1つである。
このクラスの問題に対する解決策の1つは、$K$-adaptabilityである。
機械学習に基づくノード選択戦略を提案する。
学習したノード選択戦略は、トレーニング問題と同じタイプの問題でテストした場合、バニラ、ランダムなノード選択戦略よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-20T10:43:23Z) - Neur2SP: Neural Two-Stage Stochastic Programming [3.5417030119735045]
我々はニューラルネットワークを介して期待値関数を近似する新しい方法Neur2SPを開発した。
Neur2SPはすべての問題に対して1.66秒未満で、シナリオの数が増えても高品質なソリューションを実現する。
論文 参考訳(メタデータ) (2022-05-20T22:09:22Z) - Learning for Robust Combinatorial Optimization: Algorithm and
Application [26.990988571097827]
最適化学習(L2O)は、ニューラルネットワークの強い予測力を活用することにより、最適化問題を解決するための有望なアプローチとして登場した。
本稿では,不確実な状況下で頑健な解を迅速に出力するLRCOという新しい学習ベース最適化を提案する。
その結果、LRCOは、非常に少ない複雑さで、最悪のケースコストとランタイムを大幅に削減できることがわかった。
論文 参考訳(メタデータ) (2021-12-20T07:58:50Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳(メタデータ) (2021-11-24T07:14:57Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - 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) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2~5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳(メタデータ) (2020-02-04T20:00:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。