確率的整数計画法 — 不確実性下での離散的意思決定の最適化
- 提唱者
- Dantzig, G. B.; Beale, E. M. L.
- 年
- 1955
- 種類
- Optimization under uncertainty with discrete decisions
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
確率的整数計画法(Stochastic Integer Programming, SIP)は、整数(離散)決定変数と不確実性の明示的な確率的モデリングを組み合わせた最適化フレームワークである。これは、不確実性が解消される前に一部の決定を下さなければならないという事実を考慮し、将来のシナリオの分布全体にわたる期待費用を最小化(または期待便益を最大化)する、現時点で最善の決定を求める。
手法の背後にある直感
多くの現実の意思決定は、離散的(施設を建設するか否か、作業員を割り当てるか否か)かつ不確実(需要、費用、制約は決定時に不明)である。SIPはこれら両方の課題を同時に扱う。不確実な未来を、関連する確率を持つシナリオの集合としてモデル化し、平均して最も良い性能を発揮する、あるいは最悪の結果に対するヘッジとなる整数解を見つける。確率的線形計画法とは異なり、離散構造は問題を組み合わせ論的に困難にするが、得られる決定は丸めや近似なしに直接実装可能である。
歴史学
確率的計画法は、1955年のDantzigとBealeによって独立に提案された、不確実性下での線形計画法のための二段階後続モデルに遡る。整数拡張は、1960年代から1980年代にかけて整数計画法が成熟するにつれて現れた。BirgeとLouveauxの1997年の教科書はこの分野を体系化し、Kleywegtら(2002)はサンプル平均近似を大規模確率的離散最適化の標準的な計算アプローチとして確立した。
使うべき場面
決定が本質的に離散的(二値選択、単位単位の割り当て、経路割り当て)であり、主要なパラメータが決定時に不確実である場合に、確率的整数計画法を使用する。需要不確実性下での容量計画、サプライチェーンネットワーク設計、スケジューリング、ランダム収率を伴うリソース割り当てに適している。すべての変数が連続である場合(確率的線形計画法で十分)、不確実性が無視できるか決定前に完全に観測可能である場合、問題規模が分解インフラストラクチャなしではシナリオ列挙を計算上不可能にする場合、または単一の決定論的シナリオのみが関連する場合に使用しないこと。
限界と注意点
- 計算複雑性は、シナリオ数と整数変数の増加とともに急速に増大する。大規模インスタンスはNP困難である。
- シナリオ生成には、信頼できる確率分布が必要であり、これは限定的なデータからの引き出しや推定が困難な場合がある。
- 多段階拡張(二段階以上)は、シナリオ木の指数関数的な増加に直面し、3段階を超えることはまれにしか実行可能ではない。
- モデリングスキルは、後続の実行可能性、非先取り制約、およびペナルティ構造を正しく指定するために必要とされる。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 点推定を使用するのではなく、不確実性を明示的にモデル化し、実現したシナリオに対してロバストな解を生成する。
- 離散的および二値的意思決定をネイティブに処理するため、解は事後的な丸めなしに直接実装可能である。
- 二段階フレームワークは、戦略的な第一段階の決定と運用上の第二段階の後続措置を明確に分離する。
- リソース調達、ペナルティ費用、是正スケジューリングを含む、リソースな後続構造をサポートする。
- 統計的な品質限界(SAA経由)により、実務家は定量化された信頼度でほぼ最適性を証明できる。
応用
- 確率的需要とリードタイム下でのサプライチェーンネットワーク設計
- 不確実な再生可能エネルギー出力を持つ発電拡張計画
- 変動する処置時間下での病院手術室スケジューリング
- 確率的な航空便遅延を伴う航空会社乗務員スケジューリング
- 災害前の救援物資の事前配置に関する人道ロジスティクス
- 離散的な資産選択とシナリオベースのリターンを伴う金融ポートフォリオ最適化
使い方
使い方
第一段階の問題を定式化する:不確実性が明らかになる前に、整数(または混合整数)決定変数 x を選択する。即時費用と、全シナリオにわたる期待後続費用の両方を含む目的関数を定義する。x と実行可能性条件を結びつける制約をここで指定する。
数式
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]有限個のシナリオの集合を通じて不確実性を表現する。各シナリオは、ランダムなパラメータ(需要レベル、費用、リソース利用可能性)に特定の値を割り当てる。シナリオは、履歴サンプリング、適合分布からのモンテカルロ描画、または専門家定義の代表的なケースを通じて生成できる。各シナリオは、合計が1になる確率重みを持つ。
標準的な二段階定式化では、x が固定されシナリオ xi が実現した後、後続(第二段階)問題が是正措置 y を決定する。後続問題はしばしば線形計画または整数計画である。完全なモデルは、c^T x に期待後続費用 E[Q(x, xi)] を加えたものを最小化する。
数式
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xシナリオサブ問題を解いて、x が与えられた各シナリオに対する後続費用を評価する。手法には、分枝限定法、ベンダー分解法、ラグランジュ緩和法、およびサンプル平均近似(Sample Average Approximation, SAA)法が含まれる。大規模なシナリオ木の場合、分解アルゴリズムはシナリオ間のブロック構造を利用する。
サブ問題の結果を集計して期待後続費用を推定する。SAAでは、これはS個のサンプリングされたシナリオの平均である。結果として得られる近似は、Sが増加するにつれて真の期待値に収束する。解の質に関する統計的限界は、サンプル分散から計算できる。
数式
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)最適性ギャップ、収束基準、またはSAAからの統計的信頼区間を通じて、最適性またはほぼ最適性を検証する。ギャップが許容できない場合は、シナリオ集合を精緻化し、サンプルサイズを増やし、または緩和を厳しくする。第一段階の解 x* とその期待総費用を報告する。
よくある落とし穴
- シナリオが少なすぎると過度に楽観的な解が得られ、多すぎると問題が計算上実行不可能になる。SAAの収束診断を通じてバランスを取る。
- 第二段階で実際には必要とされる整数性を無視すると、楽観的な費用推定と実行不可能な後続措置につながる。
- パラメータが相関している場合(例:相関する需要と価格)にシナリオの独立性を仮定すると、期待費用推定に系統的なバイアスが生じる。
- 多段階問題で非先取り制約を忘れると、実際には利用できない将来の情報にモデルが依存してしまう。
よくある質問
確率的整数計画法はロバスト最適化とどう違うのか?
SIPは確率重み付きシナリオ集合全体での期待費用を最小化し、一部のシナリオでは確率が低い場合に高コストを許容する。ロバスト最適化は、不確実性集合全体での最悪ケース費用を最小化し、確率的仮定をしない。SIPは確率分布を必要とするが、ロバスト最適化は不確実性集合のみを必要とする。SIPは一般的に保守性が低いが、より多くのデータが必要である。
実際にはいくつのシナリオが必要か?
問題の次元と望ましい精度に依存する。サンプル平均近似(SAA)アプローチは、最適性ギャップに関する統計的信頼区間を提供する。典型的な応用研究では、数十から数千のシナリオが使用される。収束診断(バウンド推定値の分散)が選択をガイドする。構造化された問題では、シナリオ削減技術(例:Heitsch-Romisch)がシナリオ数を大幅に削減できる。
確率的整数計画法は二段階以上を扱えるか?
はい、しかし多段階SIPは著しく困難である。シナリオ木は段階とともに指数関数的に成長し、非先取り制約は各ノードで強制されなければならない。実際には、実行可能な応用では3段階モデルが標準であるが、それ以上では、ローリングホライゾンやシナリオ木削減などの近似が通常必要とされる。
確率的整数計画法モデルを解くことができるソフトウェアは?
一般的なソルバーには、CPLEXやGurobi(AMPL、JuliaのJuMP、またはPythonのPuLP/Pyomoなどの代数モデリング言語を介して)があり、これらはシナリオ分解をサポートする。専門的な確率的計画法フレームワークには、PySP(Python)、SMPS形式ソルバー、およびSAAとプログレッシブヘッジを実装するJuliaパッケージStochasticPrograms.jlが含まれる。
確率的整数計画法は確率的混合整数計画法と同じか?
確率的整数計画法はより広範なクラスであり、確率的混合整数計画法(Stochastic Mixed-Integer Programming, SMIP)は、一方または両方の段階で一部の変数が連続で他が整数であるモデルを特に指す。SMIPは最も一般的で、実務で最も頻繁に遭遇する形式である。
関連する手法
参考文献
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN:978-1-4614-0237-4コピーしました。Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
DOI 文献を開くコピーしました。