ロバスト線形計画法 — 不確実性下での最適化
- 提唱者
- Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
- 年
- 1999–2004
- 種類
- Uncertainty-robust linear optimization
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
ロバスト線形計画法(RLP)は、古典的な線形計画法を拡張し、問題データ(コスト係数、制約係数、または右辺値)の不確実性を扱う手法である。これは、定義された不確実集合内の不確実パラメータの全ての実現値に対して、解が実行可能かつ最適に近いままであることを要求する。確率的仮定の代わりに最悪ケースの保証を用いるため、分布に関する知識が限定的な場合に実用的である。
手法の背後にある直感
通常の線形計画法は、全てのデータが正確に既知であると仮定して最良の解を見つける。実際には、係数は誤差を伴って推定、予測、または測定される。RLPは、「あり得る範囲内で不確実パラメータがどのように変動しても実行可能であり続ける最良の決定は何か?」と問う。分析者は不確実集合(ボックス、楕円体、または多面体領域)を指定し、ソルバーはその集合内の最悪ケースに対して最適となる計画を見つける。BertsimasとSimによるバジェット・オブ・アンサーティンティ(budget-of-uncertainty)定式化は、分析者が保守性を調整することを可能にする。パラメータΓ(ガンマ)は、同時にいくつの係数が変動することを許容するかを制御し、名目上のLPと完全に保守的な最悪ケースとの間を補間する。
歴史学
ロバスト最適化は、Ben-TalとNemirovski(1999)によって確固たる理論的基盤が築かれた。彼らは、楕円体不確実集合を持つ不確実線形計画問題が、扱える二次錐計画問題をもたらすことを示した。BertsimasとSim(2004)は、バジェット・オブ・アンサーティンティ(budget-of-uncertainty)フレームワークを導入した。これは、再定式化を線形計画問題のまま保ち、単一パラメータによるロバスト性の調整を可能にし、オペレーションズリサーチや工学分野での実用的な採用を大幅に拡大した。
使うべき場面
データの不確実性が現実的であるが、確率分布が不明または信頼できない場合に使用する。例としては、需要が不確実なサプライチェーン計画、予測誤差のある電力 dispatch、曖昧なリターンのポートフォリオ構築などが挙げられる。制約違反の実行可能性が全てのシナリオで譲れない場合に適切である。不確実性が目的関数の規模に対して無視できる場合、確率分布がよく特徴付けられている場合(確率的計画法が好ましい場合)、不確実パラメータの数が多すぎてロバストな対応物が扱いにくくなる場合、または最悪ケースシナリオがアプリケーションにとって非現実的に悲観的すぎる場合にRLPを避ける。
限界と注意点
- 最悪ケース指向は、極端なシナリオが発生する可能性が非常に低い場合に、過度に保守的な解を生成する可能性がある。
- 楕円体不確実集合は、扱える二次錐計画問題をもたらすが、純粋なLPではなくなり、ソルバーの要件が増加する。
- 分析者に不確実集合を指定することを要求するが、これは結果に大きく影響するモデリングの選択である。
- 違反確率のステートメントを直接提供しない。テール確率が重要な場合は、確率的計画法の方が適している。
- Γ = 0 の場合、名目上のLPに退化し、不確実性に対する保護を提供しない。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 分布仮定を必要とせずに、厳密な最悪ケースの実行可能性保証を提供する。
- Bertsimas-Simバジェット定式化は、市販のソルバーで解ける扱えるLP対応物を生成する。
- ロバスト性バジェットΓは、分析者に解の質と保守性のトレードオフを調整するための直感的なダイヤルを提供する。
- 計算効率が良い — バジェット集合に対するロバストな対応物は、元のLPと同様の複雑さを持つ。
- 特に制約違反が高コストまたは危険な問題に非常に適している。
応用
- 輸送コストと需要が不確実なサプライチェーンネットワーク設計
- 再生可能エネルギー予測の不確実性下での電力システム dispatch
- 曖昧な資産リターン範囲でのポートフォリオ最適化
- 患者の動きの不確実性下での放射線療法治療計画
- 航空機乗務員スケジューリングにおける遅延の不確実性
- 降水量と蒸発量の不確実性下での水資源配分
使い方
使い方
名目上の線形計画問題を定式化する:線形目的関数 c^T x を、線形不等式制約 Ax <= b および非負性制約の下で最小化する。どの係数(通常は制約行列のエントリ a_ij)が不確実であるかを特定する。このステップは標準的なLPモデリングに似ているが、各不確実パラメータにフラグを立てる。
数式
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0確率分布を必要とせずに、パラメータ値のあり得る範囲を捉える不確実集合Uを構築する。一般的な選択肢としては、ボックス集合(各パラメータが [a_bar - a_hat, a_bar + a_hat] の範囲で独立に変動する)、楕円体集合(Ben-Tal and Nemirovski, 1999)、およびバジェット集合(Bertsimas and Sim, 2004)がある。バジェットパラメータΓは、同時にいくつのパラメータが最悪ケースの値を取り得るかを制限する。
数式
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}各不確実制約をそのロバストな対応物に置き換える:U内の全ての実現値に対して実行可能性を要求する。これにより、元の問題は半無限計画問題(Uの各要素に対応する無限個の制約を持つ)に変換される。
数式
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i扱える決定論的等価物を導出する。バジェット不確実集合の場合、ロバストな対応物は標準的なLPまたは混合整数LPとして再定式化され、従来のソルバーで解くことができる。鍵となる再定式化は、不確実集合に対する内部最大化を線形化する補助変数を導入することである。
数式
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i標準的なソルバー(シンプレックス法または内点法)を使用して再定式化されたLPを解く。解を評価する:不確実集合全体での最悪ケースの制約違反をチェックし、ロバスト性の価格(名目上のLPに対する目的関数の増加分)を報告し、ロバスト性バジェットΓに関する感度分析を実行する。
よくある落とし穴
- Γ を高く設定しすぎると、全ての制約が同時に最悪ケースとなり、過度に保守的で高価な解が得られる。
- 不確実集合の誤指定(例:相関構造の無視)は、過剰または過小な保護につながる可能性がある。
- ロバストLPと確率的LPの混同:RLPは期待性能ではなく、最悪ケースの性能を最大化する。
- ロバスト性の価格の報告を無視すること — 保守性のコストを定量化するために、常にロバスト解の目的関数を名目上のLP解と比較する。
- 整数変数を持つ問題に、ロバスト混合整数計画の定式化に切り替えずにRLPを適用すること。後者は異なる再定式化を必要とする。
よくある質問
ロバストLPと確率的LPの違いは何ですか?
確率的LPは、確率分布を仮定してシナリオに対する期待性能を最適化する。ロバストLPは、不確実集合に対する最悪ケースの性能を最適化する。ロバストLPは分布が信頼できない場合に好まれ、確率的LPは分布がよく推定されている場合に好まれる。
ロバスト性の価格とは何ですか?
ロバスト性の価格とは、ロバスト解の目的関数値(コスト)が名目上のLP解と比較して増加する分である。BertsimasとSim(2004)は、この価格がバジェット集合の場合、不確実パラメータ数の平方根にしか比例して増加しないことを証明し、ロバスト性が驚くほど安価であることを示した。
ロバスト性バジェットΓとは何ですか?
ΓはBertsimas-Simモデルのパラメータであり、同時にいくつの不確実係数が最悪ケースの値を取り得るかを制御する。Γ = 0 は名目上のLPを回復し、Γ = n は全てのn個のパラメータが同時に変動することに対する保護を与える。分析者は通常、許容される違反確率の上限に基づいてΓを選択する。
ロバストLPは特別なソルバーを必要としますか?
いいえ。ボックス集合およびバジェット集合の場合、ロバストな対応物はそれ自体が線形計画問題であり、任意の標準LPソルバー(CPLEX、Gurobi、HiGHSなど)で解くことができる。楕円体集合は二次錐計画ソルバーを必要とするが、これも広くサポートされている。
どのような場合にロバスト混合整数計画法を使用すべきですか?
決定変数が整数でなければならない場合(例:バイナリのYes/No決定、ロットサイズ)、ロバストな対応物は整数変数を含み、ロバスト混合整数計画問題となる。不確実集合のアプローチは同じだが、再定式化とソルバーの要件がそれに応じて変化する。