論文の概要: Neur2SP: Neural Two-Stage Stochastic Programming
- arxiv url: http://arxiv.org/abs/2205.12006v1
- Date: Fri, 20 May 2022 22:09:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-05 22:10:33.156656
- Title: Neur2SP: Neural Two-Stage Stochastic Programming
- Title(参考訳): Neur2SP: ニューラルな2段階確率プログラミング
- Authors: Justin Dumouchelle, Rahul Patel, Elias B. Khalil, Merve Bodur
- Abstract要約: 我々はニューラルネットワークを介して期待値関数を近似する新しい方法Neur2SPを開発した。
Neur2SPはすべての問題に対して1.66秒未満で、シナリオの数が増えても高品質なソリューションを実現する。
- 参考スコア(独自算出の注目度): 3.5417030119735045
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic programming is a powerful modeling framework for decision-making
under uncertainty. In this work, we tackle two-stage stochastic programs
(2SPs), the most widely applied and studied class of stochastic programming
models. Solving 2SPs exactly requires evaluation of an expected value function
that is computationally intractable. Additionally, having a mixed-integer
linear program (MIP) or a nonlinear program (NLP) in the second stage further
aggravates the problem difficulty. In such cases, solving them can be
prohibitively expensive even if specialized algorithms that exploit problem
structure are employed. Finding high-quality (first-stage) solutions -- without
leveraging problem structure -- can be crucial in such settings. We develop
Neur2SP, a new method that approximates the expected value function via a
neural network to obtain a surrogate model that can be solved more efficiently
than the traditional extensive formulation approach. Moreover, Neur2SP makes no
assumptions about the problem structure, in particular about the second-stage
problem, and can be implemented using an off-the-shelf solver and open-source
libraries. Our extensive computational experiments on benchmark 2SP datasets
from four problem classes with different structures (containing MIP and NLP
second-stage problems) show the efficiency (time) and efficacy (solution
quality) of Neur2SP. Specifically, the proposed method takes less than 1.66
seconds across all problems, achieving high-quality solutions even as the
number of scenarios increases, an ideal property that is difficult to have for
traditional 2SP solution techniques. Namely, the most generic baseline method
typically requires minutes to hours to find solutions of comparable quality.
- Abstract(参考訳): 確率プログラミングは不確実性の下で意思決定のための強力なモデリングフレームワークである。
本研究では,最も広く応用され研究されている2段階確率型プログラム (2SP) について検討する。
2spsの解くには、計算上難解な期待値関数の評価が必要である。
さらに、混合整数線形プログラム(MIP)または非線形プログラム(NLP)を第2段階で持つと、さらに問題を悪化させる。
このような場合、問題構造を利用する特殊なアルゴリズムが用いられる場合でも、それらの解決は違法にコストがかかる可能性がある。
このような設定では、問題構造を活用せずに高品質な(第1ステージ)ソリューションを見つけることが重要です。
ニューラルネットワークを用いて期待値関数を近似する新しい手法Neur2SPを開発し,従来の広範囲な定式化手法よりも効率的に解ける代理モデルを得る。
さらに、Neur2SPは問題構造、特に第2段階の問題については仮定せず、既成の解法とオープンソースライブラリを使って実装することができる。
異なる構造を持つ4つの問題クラス(MIPおよびNLP第2ステージ問題を含む)のベンチマーク2SPデータセットに対する広範な計算実験は、Neur2SPの効率(時間)と有効性(ソリューション品質)を示している。
具体的には,提案手法はすべての問題に対して1.66秒未満の時間を要し,シナリオの数が増えても高品質なソリューションを実現する。
すなわち、最も一般的なベースラインメソッドは通常、同等の品質のソリューションを見つけるのに数分から数時間かかる。
関連論文リスト
- Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳(メタデータ) (2024-06-11T19:59:05Z) - Genetic-based Constraint Programming for Resource Constrained Job
Scheduling [5.068093754585243]
資源制約されたジョブスケジューリングは、鉱業に起源を持つ計算の最適化問題である。
既成のソリューションはこの問題を合理的な時間枠で十分解決できない。
本稿では,制約プログラミングの効率的な探索手法を探索する遺伝的プログラミングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-01T09:57:38Z) - Deep Learning for Two-Stage Robust Integer Optimization [15.876446950057389]
カラム・アンド・制約生成アルゴリズムの深層学習型インスタンス化であるNeur2ROを提案する。
カスタム設計のニューラルネットワークは、第2ステージ問題の最適値と実現可能性を評価するために訓練される。
Neur2ROは高品質なソリューションを迅速に製造し、2段階のクナップサックにおける最先端の手法、資本予算、施設配置問題に優れる。
論文 参考訳(メタデータ) (2023-10-06T16:11:46Z) - An Efficient Learning-Based Solver for Two-Stage DC Optimal Power Flow with Feasibility Guarantees [4.029937264494929]
本稿では,より効率的かつ最適な方法で2段階問題の解法を提案する。
ゲージマップと呼ばれるテクニックが学習アーキテクチャ設計に組み込まれ、学習したソリューションがネットワークの制約に対して実現可能であることを保証する。
論文 参考訳(メタデータ) (2023-04-03T22:56:08Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。
$nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
論文 参考訳(メタデータ) (2021-12-01T22:55:23Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
本稿では,ベイズニューラルネットワークを用いた高次元レベル集合推定問題を解く新しい手法を提案する。
各問題に対して対応する理論情報に基づく取得関数を導出してデータポイントをサンプリングする。
合成データセットと実世界データセットの数値実験により,提案手法は既存手法よりも優れた結果が得られることが示された。
論文 参考訳(メタデータ) (2020-12-17T23:21:53Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。