確率的混合整数計画法 — 不確実性下における離散および連続意思決定の最適化
- 提唱者
- Birge, J. R.; Louveaux, F.; Sen, S.
- 年
- 1990s–2000s
- 種類
- Stochastic optimization model
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
確率的混合整数計画法(SMIP)は、コスト、需要、容量などの主要パラメータが不確実であり、シナリオ集合上の確率分布としてモデル化される場合に、バイナリ、整数、および連続の意思決定の最適な組み合わせを見つける最適化フレームワークである。これは、シナリオツリーまたは期待値目的関数を埋め込むことによって古典的なMIPを拡張し、組み合わせ制約を尊重しながら不確実性に対するヘッジを行う。
手法の背後にある直感
多くの実際の計画問題では、イエス/ノーまたは整数個の選択(施設を建設するかどうか、車両を整数個割り当てるかなど)を強制されるが、将来は不確実である。SMIPは、考えられる将来のシナリオのコレクションを考慮し、不確実性が明らかになる前に第一段階のコミットメントを選択することで、すべてのシナリオにわたる期待コストを最小化または期待利益を最大化する。
歴史学
確率的計画法は、Dantzig(1955)とBeale(1955)による二段階LPとして起源を持つ。混合整数拡張は、LaporteとLouveaux(1993)による整数リカバリへのL字型法の適応と、BirgeとLouveauxの1997年の教科書での包括的な扱いにより、1990年代に顕著になった。SenとHigleのC3/D2アルゴリズム(2005)は、スケーラブルなSMIPソルバーを進歩させ、オペレーションズリサーチ内の成熟した分野として確立した。
使うべき場面
意思決定に離散またはバイナリの選択(投資/投資しない、開くユニット数)が含まれ、主要な入力パラメータが定量化可能な確率分布として実際に不確実である場合にSMIPを使用する。需要の不確実性下でのサプライチェーンネットワーク設計、エネルギー容量拡張、医療施設計画、および災害対応の事前配置に理想的である。すべての意思決定が連続である場合(代わりに確率的LPを使用)、不確実性を意味のある分布として定量化できない場合、不確実性を表現するために必要なシナリオ数が手に負えないモデルサイズにつながり、分解が利用できない場合、または意思決定の質に必要なシミュレーションベースのヒューリスティックで十分な場合は使用しない。
限界と注意点
- 計算複雑性は、シナリオ数と整数変数の数とともに組み合わせ的に増加する。大規模なインスタンスは、効果的な分解なしでは手に負えない可能性がある。
- 明示的な確率分布またはシナリオセットが必要である。不確実性モデルの誤指定は、サンプル外でパフォーマンスの悪い解につながる。
- 二段階定式化は多期間の意思決定を単純化しすぎる可能性がある。多段階SMIPは著しく困難である。
- 第二段階の整数リカバリは、標準的なベンダーカットによって利用される凸性を破壊するため、特殊な整数L字型カットが必要となる。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 単一の整合性のある最適化モデルで、不確実性下での組み合わせ離散意思決定を処理する。
- すべてのシナリオにわたる期待パフォーマンスのバランスをとる、ヘッジされた第一段階計画を生成する。
- VSSおよびEVPI指標は、確率的モデリングの価値の透明な正当化を提供する。
- 分解アルゴリズム(L字型、プログレッシブヘッジング)は、大規模なシナリオ集合にスケールする。
- 商用ソルバー(CPLEX、Gurobi)およびモデリング言語(AMPL、Pyomo)で広くサポートされている。
応用
- 不確実な顧客需要とバイナリの施設立地決定を伴うサプライチェーンネットワーク設計。
- 不確実な再生可能エネルギー発電と負荷成長を伴う電力容量拡張計画。
- 疫学的不確実性下での医療システムリソース配分(整数スタッフ、バイナリ診療所開設)。
- 災害シナリオ前の離散的な救援物資の人道的ロジスティクス事前配置。
- 市場の不確実性下での取引コストと整数ロットサイズ制約を伴う金融ポートフォリオ最適化。
- 不確実なフライト遅延を伴う航空会社の乗務員スケジューリング(バイナリ割り当て変数)。
使い方
使い方
意思決定変数(不確実性が明らかになる前に作成される第一段階の決定x(それらの中に整数および/またはバイナリが含まれる)、およびシナリオxiが発生した後に作成される第二段階のリカバリ変数y(xi))を特定する。目的係数、制約行列、および不確実なパラメータの確率分布または離散シナリオセットを指定する。
基礎となる分布を近似する、関連する確率{p_1, ..., p_S}を持つ有限シナリオ集合{xi_1, ..., xi_S}を構築する。シナリオは、履歴データ、専門家の意見、ラテン超方格サンプリング、またはモーメントマッチング法から導出できる。シナリオの質は、解の質に直接影響する。
決定論的等価物を定式化する:第一段階の制約と整数性を満たす制約の下で、c'x + sum_s p_s Q(x, xi_s)を最小化する。Q(x, xi_s)は第二段階の値関数であり、xとシナリオxi_sが与えられた場合のリカバリアクションの最適コストである。結合されたプログラムは、シナリオ数とともにサイズが増加する大規模なMIPである。
数式
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}分解アルゴリズムを使用して解く — 第二段階が凸の場合のL字型法(ベンダー分解)、シナリオサブ問題を持つ枝刈り法、またはシナリオ並列分解のためのプログレッシブヘッジング。第二段階の整数性は、追加のカット(整数L字型カット、リフトアンドプロジェクション)を必要とする。最新のソルバー(CPLEX、コールバック付きGurobi、またはSMIP固有のライブラリ)は、これらのルーチンを実装している。
確率的解の値(VSS = EEV - RP)と完全情報の期待値(EVPI = RP - WS)を評価する。ここで、RPはリカバリ問題の最適値、EEVは決定論的平均値解を使用する期待コスト、WSは待機して見る値である。これらの指標は、不確実性を明示的にモデル化することの利点を定量化する。
よくある落とし穴
- 少なすぎるシナリオを使用すると不確実性が過小評価され、過度に確信度の高い解が得られる。多すぎるシナリオを使用すると、モデルが計算上実行不可能になる。
- 第一段階と第二段階の変数の役割を混同すると、情報開示のタイミングを尊重しない定式化につながる。
- 期待値解(確率性を無視)に依存することは、著しく最適でなくなる可能性がある。常にVSSを計算して、SMIPの労力の価値を正当化する。
- リカバリ段階で実際には存在する整数性を無視すると、実際には実行不可能な緩和解が得られる。
- SMIP分解フレームワークでは、MIPのソルバーデフォルト設定(分岐優先順位、カット戦略)の調整が必要になることが多い。
よくある質問
SMIPは通常の混合整数計画法とどう違うのか?
通常のMIPは、固定された既知のパラメータ下で最適化を行う。SMIPは、不確実なパラメータを確率を伴うシナリオ集合として明示的にモデル化し、すべてのシナリオにわたる期待パフォーマンスを最適化し、不確実性が明らかになる前に第一段階の決定が行われることを保証する。
いくつのシナリオが必要か?
普遍的なルールはない。問題によっては10〜50個のシナリオで安定した第一段階の決定が十分な場合もあるが、他の問題では数千個が必要となる場合もある。シナリオ削減技術と安定性テスト(シナリオを追加しても最適解が変わらないかを確認する)は、適切性を判断するのに役立つ。
L字型法とは何か?
L字型法は、確率的計画法に適応されたベンダー分解である。第一段階の変数とシナリオサブ問題に関するマスターMIPを反復的に解き、収束するまでマスターに最適性と実行可能性カットを追加する。整数リカバリの場合、標準的なベンダーカットの代わりに整数L字型カットが使用される。
プログレッシブヘッジングをL字型法の代わりにいつ使用すべきか?
プログレッシブヘッジングは、サブ問題構造ではなくシナリオごとに分解するため、並列コンピューティングに適している。シナリオが多く、サブ問題が大きい場合、およびアルゴリズムをクラスターで実行できる場合に好ましい。L字型法は、一般的に、より少なく、構造化されたシナリオに適している。
SMIPは2段階以上を扱えるか?
はい、しかし多段階SMIPは段階数とともに指数関数的に増加するシナリオツリーを必要とし、分解は著しく複雑になる。実際には、ほとんどの応用SMIPモデルは2段階を使用し、ローリングホライズンまたは集約によって多期間ダイナミクスを近似する。
関連する手法
参考文献
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN:9780387982175コピーしました。Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
DOI 文献を開くコピーしました。