Skip to content
検索結果に戻る

ロバスト混合整数計画法 — 不確実性下での整数変数を含む最適化

提唱者
Ben-Tal & Nemirovski; Bertsimas & Sim
年
1998–2004
種類
Deterministic robust reformulation of MIP under uncertainty
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

ロバスト混合整数計画法(RMIP)は、混合整数計画法とロバスト最適化を組み合わせることで、不確実なパラメータが存在する状況でも実行可能かつ準最適な解を見つけ出す手法です。RMIPは、固定されたデータを仮定するのではなく、明示的な不確実性集合を用いて、不確実な入力の敵対的または最悪の実現値に対して決定を保護します。これにより、整数決定の組み合わせ構造を維持しつつ、保守主義の度合いを制御します。

手法の背後にある直感

従来の混合整数計画法では、すべてのデータが正確に既知であると仮定されますが、実際にはコスト、需要、処理時間などは変動します。RMIPは、「不確実なパラメータが定義された範囲内で最悪の妥当な値を取る場合、どのような整数および連続決定が最適か」という問いに答えます。不確実性を最適化モデルに直接組み込むことで、RMIPは複数の確率的シナリオに頼ることなく、データ変動に対して免疫のある計画を生成します。Bertsimas-Simの不確実性バジェットアプローチにより、実務家は完全なロバスト性と平均ケース効率の間で調整を行い、保護とコストのトレードオフを明確にすることができます。

歴史学

連続問題に対する扱いやすいパラダイムとしてのロバスト最適化は、1990年代後半にBen-TalとNemirovskiによって確立されました。BertsimasとSim (2004) は、線形計画法に不確実性バジェット集合を導入し、線形な扱いやすさを維持する形で拡張しました。その後の研究で、このフレームワークが整数計画法と統合され、RMIPが誕生しました。RMIPは2010年代を通じて、サプライチェーン、エネルギー、輸送の研究で広く採用されるようになりました。

使うべき場面

RMIPは、決定が整数またはバイナリの選択(施設配置、ロットサイジング、ネットワーク設計、スケジューリング)を伴い、一部の入力パラメータが不確実であるものの、確率分布が利用できないか信頼できない場合に利用します。制約違反が許容できない(厳格な実行可能性要件)場合や、期待値最適化よりも保守的だが決定論的な保証が好まれる場合に適切です。不確実性の分布が十分に特徴付けられており、標本平均近似や確率MIPが実行可能な場合、すべての決定変数が連続である場合(代わりにロバストLPを使用)、または不確実性集合が大きすぎて分解戦略なしではモデルが扱えなくなる場合には使用しないでください。

限界と注意点

  • 設計上保守的である — 最悪ケースの目的関数値は、確率計画の期待ケースの目的関数値よりも通常悪い。
  • 適切な不確実性集合の選択にはドメイン知識が必要である。不適切に選択された集合は、過剰な保護または不十分な保護につながる。
  • ロバストな再定式化は、モデルサイズ(追加の変数と制約)を大幅に増加させる可能性があり、大規模なインスタンスでは計算負荷が増大する。
  • 解の性能に関する確率的な記述を提供しない。確率的リスク尺度が必要な場合は、確率MIPの方が適している。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 不確実なパラメータの確率分布を必要とせず、決定論的な最悪ケースの実行可能性保証を提供する。
  • 不確実性バジェット(Gamma)パラメータにより、ロバスト性と最適性のトレードオフを直感的かつ調整可能に制御できる。
  • 再定式化によりMIP構造が維持されるため、成熟した商用ソルバーや分枝切除技術を利用できる。
  • ネットワーク設計、施設配置、生産スケジューリングなどの困難な組み合わせ問題に適用可能。
  • 多数のシナリオを持つ完全な確率MIPよりも計算上扱いやすい。

応用

  • 不確実な需要とリードタイムの下でのサプライチェーンネットワーク設計
  • 不確実な再生可能エネルギー発電を伴うエネルギーシステム容量拡張計画
  • 患者需要の不確実性下での医療施設配置
  • 不確実なフライト遅延を伴う航空会社の乗務員スケジューリング
  • 不確実なコストと処理時間を伴う製造ロットサイジング
  • 不確実なトラフィック量を伴う電気通信ネットワークルーティング

使い方

使い方

1

名目MIPを定式化します。決定変数(バイナリまたは整数 y、連続 x)、目的関数、および制約を特定します。どのパラメータ(コスト係数、右辺値、技術行列の要素)が不確実であり、保護する必要があるかを明確にします。

2

不確実なパラメータに対する不確実性集合 U を定義します。一般的な選択肢としては、ボックス集合(各パラメータの区間範囲)、楕円体集合(相関のある不確実性)、またはBertsimas-Simのバジェット集合(最大Gamma個のパラメータが同時に逸脱)があり、Gammaが保守主義を制御します。

3

各不確実な制約をそのロバスト対応物で置き換えます。これは U 内のすべての実現値に対して成立する必要があります。バジェット不確実性の場合、これは扱いやすい再定式化をもたらします。元の制約は、最悪ケースの偏差の合計を制御するペナルティ項で拡張されます。結果として、より大規模ではあるものの、依然としてMIPとして扱いやすいモデルが得られます。

4

ロバストに再定式化されたMIPを、標準的な分枝限定法または分枝切除法ソルバー(例:CPLEX、Gurobi、SCIP)で解きます。この再定式化は、y の整数性要件を保持します。大規模なインスタンスの場合、Benders分解法や切除平面法を用いて問題を分解することができます。

5

ロバスト解を評価します。(a) 名目パラメータおよび最悪ケースパラメータの下での目的関数値を計算する、(b) Monte Carloシナリオを用いた確率計画解と比較ベンチマークを行う、(c) ロバスト性の価格(不確実性保護のために支払われる追加コスト)を報告する、という方法で行います。

よくある落とし穴

  • Gamma=0(不確実性バジェットなし)を選択すると、名目MIPが再現され、保護は提供されない。Gammaが大きすぎると、過度に保守的で運用上非現実的な解につながる。
  • すべてのパラメータを同時に不確実として扱うと、再定式化が扱いにくくなる可能性がある。選択的に保護すべき重要な不確実パラメータを特定する。
  • 不確実性の相関構造を無視すると、過度に悲観的な不確実性集合になる可能性がある。相関が既知の場合は楕円体集合が望ましい。
  • 最悪ケースの目的関数値のみを報告し、名目または確率的ベンチマークと比較しないと、解の品質の全体像が不完全になる。

よくある質問

RMIPは確率的混合整数計画法とどう異なりますか?

確率的MIPは確率分布を使用し、サンプリングされたシナリオ全体での期待性能を最適化しますが、RMIPは分布情報を必要とせずに不確実性集合内の最悪ケースに対して保護します。RMIPは単一の決定論的なロバスト解を提供しますが、確率的MIPは平均的に良好なポリシーを提供します。

「ロバスト性の価格」とは何ですか、また通常どのくらいの大きさですか?

ロバスト性の価格とは、名目(不確実性なし)最適値と比較した目的関数値の増加率です。BertsimasとSimは、それがGammaに対してほぼ線形に増加するが、一般的なバジェット値では控えめであり、実用的なアプリケーションではしばしば5〜15%であると示しています。

RMIPは不確実なコスト係数だけでなく、不確実な右辺値も扱えますか?

はい。制約の右辺の不確実性はロバストな実行可能性制約につながり、目的関数係数の不確実性はロバストな最適性に影響します。両方とも不確実性バジェットのフレームワーク内で同時に扱うことができますが、再定式化の構造は異なります。

RMIPは標準的なMIPソルバーで解けますか?

Bertsimas-Simのバジェット集合の場合、ロバストな再定式化はMIPのままであり、CPLEXやGurobiなどのソルバーで直接解くことができます。楕円体不確実性集合は混合整数二次錐計画(MISOCP)を生成しますが、これも現代のソルバーでサポートされています。

不確実性バジェット集合よりもボックス不確実性集合を優先すべきなのはどのような場合ですか?

ボックス集合は、すべてのパラメータが同時に極端な値に逸脱することに対して保護しますが、これはしばしば過度に保守的です。すべてのパラメータの同時最悪ケース偏差が起こりにくい場合には、バジェット集合(Gamma)が好まれます。これは、より保守的でなく、より費用対効果の高い解をもたらすためです。

関連する手法

参考文献

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    DOI 文献を開く
    コピーしました。
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN:9780691143682
    コピーしました。