Skip to content
検索結果に戻る

ロバスト整数計画 — 不確実性下における整数制約付き最適化

提唱者
Bertsimas, D. and Sim, M.
年
2003
種類
Deterministic robust optimization with integer variables
系統
Simulation / optimization

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

文字サイズ

何をする手法か?

ロバスト整数計画(RIP)は、指定された不確実集合内のすべてのシナリオで実行可能かつ準最適解となる整数解またはバイナリ解を見つける。データの正確な知識を仮定するのではなく、RIPは不確実なコストまたは制約係数の最悪ケースの実現に対してヘッジを行い、入力が公称値から逸脱した場合でもうまく機能することが保証された決定を提供する。

手法の背後にある直感

現実世界の多くの決定(生産スケジュール、ネットワーク設計、リソース割り当て)は、整数(半単位を生産したり、半施設を建設したりすることはできない)と不確実なデータ(コスト、需要、移動時間は変動する)を伴う。古典的な整数計画法は不確実性を無視し、入力が推定値と異なる場合にひどく失敗する可能性のある解を生成することがある。ロバスト整数計画法は、不確実集合を通じてこの不確実性を明示的にモデル化し、最悪ケースで最もよく機能する整数解を見つける。Bertsimas-Simアプローチは、不確実性予算パラメータを使用して保守性を制御する。予算がゼロの場合、問題は決定論的IPに還元される。予算が増加するにつれて、解はデータ摂動に対してますます保護されるようになるが、目的値のコストがかかる。

歴史学

ロバスト離散最適化の体系的な研究は、BertsimasとSimが2003年の論文で離散問題に対する不確実性予算モデルを導入したことで進展した。これは、Ben-TalとNemirovski(1998年)およびEl GhaouiとLebret(1997年)による以前のロバストLP研究に基づいている。BertsimasとSimは、予算不確実性下での整数計画のロバストな対応物が実行可能なMIPであり続けることを示し、物流、ネットワーク設計、スケジューリングにおける広範な応用を促進した。Ben-Tal、El Ghaoui、Nemirovskiによる2009年のモノグラフは、連続および離散設定全体にわたるロバスト最適化の理論的基盤を統合した。

使うべき場面

決定が離散的な選択(バイナリ割り当て、ネットワーク設計、スケジューリング、ロットサイズ決定)を伴い、入力データが不確実であるが既知の集合内で制限されている場合に、ロバスト整数計画法を使用する。不確実性の確率分布が不明または信頼性が低く、最悪ケースの保証が必要な場合に、確率的整数計画法よりも好ましい。不確実性が純粋に確率的で分布がよく推定されている場合(確率的計画法を使用)、問題が純粋に連続である場合(ロバスト線形計画法を使用)、不確実集合が過度に保守的でロバスト性の価格が許容できない場合、または問題サイズが公称整数計画法さえも実行不可能にする場合には、RIPを使用しない。

限界と注意点

  • 最悪ケースの方向性は過度に保守的になる可能性があり、敵対的なシナリオが発生する可能性が低い場合でも、決定論的な最適解よりも大幅に高い目的値を持つ解を生成する。
  • 実行可能性は不確実集合の選択に依存する。一般的な凸または非凸集合は、ロバストな対応物を計算上困難にする可能性がある。
  • 確率情報を自然に組み込まない。まれだが影響の大きいイベントは、起こりうる摂動と同じ扱いを受ける。
  • 大規模なロバスト整数計画問題は、特に多数の不確実なパラメータを持つ問題では、依然として計算コストが高くなる可能性がある。
  • 適切な不確実集合と予算レベルの選択には、ドメインの専門知識が必要であり、結果に大きく影響する可能性がある。

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

強み

  • 不確実なパラメータの確率分布の知識を必要とせずに、決定論的な最悪ケースの保証を提供する。
  • Bertsimas-Simの不確実性予算フレームワークは、ロバストな対応物を実行可能に保つ — しばしば公称問題と同様のサイズの標準的なMIPとなる。
  • 保守性のレベルは、単一の予算パラメータGammaを通じて容易に制御でき、保護とコストの間の明示的なトレードオフ分析を可能にする。
  • 物流、エネルギー、金融、通信、スケジューリングなど、幅広い分野に適用可能。
  • 最悪ケースシナリオが制限され検証可能であるため、解は実際に応用可能である。

応用

  • 不確実な需要または移動時間下でのロバストな設備配置およびネットワーク設計
  • 不確実な処理時間または収率率を伴うロットサイズ決定および生産スケジューリング
  • 不確実な資産リターンを伴うカーディナリティ制約付きポートフォリオ最適化
  • 不確実な災害パラメータ下での緊急対応および人道支援物流
  • 不確実な再生可能出力によるエネルギーシステム計画(ユニットコミットメント、発電拡張)
  • 不確実なトラフィック需要下での通信ネットワークルーティング

使い方

使い方

1

不確実なパラメータを持つ整数計画問題を定式化する。不確実集合内のすべての実現に対して保持されなければならない制約の下で、最悪ケースの目的を最小化(または最大化)する。決定変数xは整数またはバイナリでなければならず、問題は内側の問題が最悪ケースシナリオを選択する最小最大(または最大最小)のバイレベル構造としてキャストされる。

数式
\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} c(\xi)^\top x \quad \text{s.t.} \quad A(\xi)x \leq b,\; x \in \mathbb{Z}^n
2

パラメータ変動の可能な範囲を捉える不確実集合Uを定義する。一般的な選択肢には、ボックス集合(パラメータごとの独立した区間境界)、楕円体集合(相関不確実性)、およびBertsimas-Simの不確実性予算集合(最大Gamma個のパラメータが同時に公称値から逸脱する)が含まれる。予算Gammaは、保守性の主要なレバーである。

数式
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})
3

内側の最悪ケース最大化を双対化または再定式化して、単一レベルの混合整数計画問題を得る。不確実性予算モデルの下では、ロバストな対応物は補助的な連続変数と線形制約を導入し、標準的な分岐限定法または分岐カット法ソルバーの実行可能性を指数関数的なシナリオ列挙なしに維持する。

4

再定式化されたロバスト整数計画問題を、標準的なMIPソルバー(CPLEX、Gurobi、SCIP)またはロバストな境界手続きを備えた特殊な分岐限定法を使用して解く。大規模インスタンスの場合、Benders分解や列・制約生成などの分解法を、マスター整数問題と敵対的サブ問題を分離するために適用できる。

5

ロバスト解を決定論的最適解および一連のサンプル外シナリオに対して評価する。ロバスト性の価格(ロバスト解と公称解の目的値のギャップ)を報告し、ロバスト解が最悪ケースシナリオの下ですべての制約を満たすことを検証する。Gammaに関する感度分析は、保護レベルと解コストのトレードオフをガイドする。

よくある落とし穴

  • 不確実性予算Gammaを高く設定しすぎると、極端に保守的で実用上無用な解が得られる。過去の偏差頻度に合わせてGammaを調整することが推奨される。
  • 選択された不確実集合に対してロバストな対応物の再定式化が有効であることを検証しないこと — 一部の再定式化は特定の集合タイプ(例:予算集合、楕円体集合ではない)にのみ適用される。
  • ロバスト整数計画法と確率的整数計画法を混同すること。RIPは期待値を最適化せず、シナリオツリーや確率分布を必要としない。
  • ロバスト性の価格分析を無視すること — 実務家は、保護がコストに見合うかどうかを判断するために、常にロバスト解と公称解の目的値を比較すべきである。
  • 不確実性が右辺に非線形に影響を与える問題にRIPを適用する際に、結果のサブ問題が実行可能であり続けることを検証しない。

よくある質問

ロバスト整数計画法は確率的整数計画法とどう違うのか?

確率的整数計画法は、シナリオの確率分布にわたる期待性能を最適化し、通常はシナリオツリーを必要とする。ロバスト整数計画法は、不確実集合にわたる最悪性能を最適化し、確率分布を必要としない — 不確実性の境界のみを必要とする。RIPは厳密な実行可能性保証を提供し、確率的IPは確率的な保証を提供する。

不確実性予算とは何か、そしてどう選ぶのか?

予算Gammaは、同時に公称値から逸脱する不確実パラメータの数を制限する。Gammaがゼロの場合、モデルは決定論的IPに還元される。Gammaが増加すると、解はよりロバストになるがコストが高くなる。実用的なルールは、過去のデータを使用してGammaを設定することである。時間ウィンドウで最大k個のパラメータが通常逸脱する場合、Gammaをkに設定する。あるいは、BertsimasとSimは、与えられたGammaに対する制約違反の確率的境界を提供する。

整数計画のロバストな対応物は依然として整数計画なのか?

はい。不確実性予算モデルの下では、ロバストな対応物は追加の連続補助変数と線形制約を導入するが、元の決定変数の整数性を維持する。結果は、市販のソルバーで解くことができる標準的なMIPとなる。

ロバスト整数計画法はいつ計算上実行可能か?

ボックス集合、予算集合、多面体集合など、双対問題が閉形式またはLP表現可能な解を持つ不確実集合に対して実行可能性が成り立つ。整数計画における楕円体不確実性は、一般に困難な二次錐制約につながる。多数の整数変数と大きな不確実集合を持つ問題では、依然として分解法が必要になる場合がある。

ロバスト整数計画法は複数の目的を扱えるか?

はい、ロバスト多目的整数計画法に拡張することで、各目的がロバストに扱われる。これはロバストなパレートフロンティアにつながる。あるいは、実務家は目的をスカラー化(重み付き和またはイプシロン制約)し、結果の単一目的問題に標準的なRIPを適用する。

関連する手法

参考文献

  1. Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.

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

    ISBN:9780691143682
    コピーしました。