決定版整数計画法 — 整数決定変数による厳密な最適化
- 提唱者
- Ralph E. Gomory
- 年
- 1958
- 種類
- Exact combinatorial optimization
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
決定版整数計画法(Deterministic Integer Programming, DIP)は、一部または全ての決定変数が整数値を取る必要があり、目的関数および制約条件のデータが完全に既知(決定論的)である問題に対して、最良の解を見つける数学的最適化アプローチである。これは、整数計画法の古典的かつ非確率的な形式であり、1950年代後半からオペレーションズ・リサーチおよび組合せ最適化の基礎となっている。
手法の背後にある直感
多くの現実世界の問題における意思決定は、本質的に離散的である。例えば、施設を開設するかしないか、作業員をシフトに割り当てるか割り当てないか、といった具合である。連続最適化手法では、これらの整数値要件を強制することはできない。決定版整数計画法は、変数を整数に制限することでこれを扱い、その間、コスト、容量、需要といった全ての問題パラメータは確実に既知とされる。その結果、確実性の仮定の下で証明可能な最適解が得られ、確率的およびロバストな変種と比較する際の基準となる定式化となる。
歴史学
整数計画法は、1950年代後半に線形計画法から出現した。Ralph Gomoryによる1958年の切除平面アルゴリズムは、最初の体系的な厳密解法であった。分岐限定法(Land and Doig, 1960)と並行して、これらのアプローチがこの分野を定義した。不確実性を考慮した変種が普及するにつれて、「決定論的」という形容詞は、確率的整数計画法(Birge and Louveaux, 1997)と区別するために古典的な定式化を指すようになり、標準的な用語となった。
使うべき場面
決定版整数計画法を使用すべき場合:(1) 決定変数が本質的に離散的である(割り当て、スケジューリング、施設配置、ビンパッキング、ネットワーク設計);(2) 全ての問題パラメータが確実に既知であるか、または点推定値として信頼できる推定が可能である;(3) 厳密な最適解が必要であり、ヒューリスティックな近似ではない場合。使用すべきでない場合:パラメータが不確実またはシナリオ依存である(代わりに確率的整数計画法またはロバスト整数計画法を使用);問題規模が大きすぎて分岐限定法が計算上実行不可能であり、ヒューリスティックで許容できる場合;変数が真に連続である(LPを使用);または複数の相反する目的を同時にバランスさせる必要がある(多目的整数計画法を使用)。
限界と注意点
- 全ての問題パラメータが正確に既知であると仮定する — 現実世界の不確実性は設計上無視される。
- 一般にNP困難であり、最悪ケースの解法時間は問題サイズに対して指数関数的に増加する。
- 大規模な組合せ問題では、現代のソルバーを使用しても、計算に数時間または数日を要する場合がある。
- モデル定式化の質(制約の引き締め、対称性の破壊)が解法時間に大きく影響する。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 決定論的モデルの仮定の下で、証明可能な最適解を保証する。
- 連続法では扱えない、離散的で組合せ的な意思決定構造を自然に扱える。
- 成熟した、非常に効率的な商用およびオープンソースソルバー(CPLEX, Gurobi, SCIP)によってサポートされている。
- 最適性ギャップの証明を提供し、大規模インスタンスにおける原理的な早期終了を可能にする。
- ヒューリスティックおよび確率的変種を比較するための、ゴールドスタンダードベンチマーク定式化として機能する。
応用
- 離散的な機械または労働リソースを用いた生産計画およびスケジューリング
- 施設配置:どの倉庫または工場を開設するかを決定する
- 輸送および物流における車両ルーティングおよび乗務員スケジューリング
- 資本予算:分割不可能な投資プロジェクトのポートフォリオを選択する
- 固定リンク確立コストを伴う電気通信ネットワーク設計
- 医療スタッフのロースタリングおよび手術室スケジューリング
使い方
使い方
最適化モデルを定義する。これは、整数決定変数の線形結合として最小化(または最大化)される目的関数であり、一連の線形不等式または等式制約に従う。全ての係数(c, A, b)は固定かつ既知であり、これが定式化を決定論的なものにしている。二値変数(0/1)は、Yes/Noの決定のための特別なケースである。
数式
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n一時的に変数が連続値を取ることを許容するLP緩和問題を解く。これにより、整数目的関数の下界が得られる。LP緩和解が既に整数値であれば、それはIPの最適解である。そうでなければ、分岐が開始される。
数式
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0LP緩和解から分数を取る変数を選択し、一方の分岐では床関数(x_j <= floor value)を、もう一方の分岐では天井関数(x_j >= ceil value)を追加して実行可能領域を分割し、再帰的に解かれる2つのサブ問題を生成する。
数式
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil各サブ問題のLP緩和問題を解いて界を得る。あるノードの界が既知の最良整数解(incumbent)よりも悪い場合は、それを枝刈りする。サブ問題がincumbentよりも良い整数実行可能解を生成した場合は、incumbentを更新する。このプロセスは、分岐限定法(branch-and-bound)探索木を形成する。
数式
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}切除平面法(cutting-plane methods) — 特にGomoryカット — は、LPシンプレックス表から、全ての整数解を満たすが現在の分数LP解によって満たされない追加の線形不等式を導出する。これらのカットを追加することでLP緩和が引き締められ、分岐が減少する。現代のソルバーは、分岐限定法とカットを、分岐カット法(branch-and-cut)フレームワークで組み合わせている。
数式
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}アルゴリズムは、全ての未解決ノードが枝刈りされるか、整数解を生成するまで終了する。終了時のincumbentは、証明可能な最適整数解である。ソルバーはまた、最良界とincumbentの間のギャップを報告し、これは大規模問題に対する停止基準として使用できる。
数式
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*よくある落とし穴
- 不確実なパラメータを決定論的な点推定値として扱うと、実際にはうまく機能しない解が得られる可能性がある — DIPを適用する前にこの仮定を検証すること。
- 弱いLP緩和(大きな整数性ギャップ)は、巨大な分岐限定木につながる;大規模化する前に、有効な不等式と再定式化に投資すること。
- ビッグM定式化による二値変数の爆発は、LP緩和を数値的に不安定にする可能性がある;よりタイトな制約の再定式化を優先すること。
- ゼロでないギャップ許容値を使用した際の、実行可能性と最適性の混同 — 常に目的値と共にギャップを報告すること。
- モデルにおける対称性(例:同一の機械または作業員)を無視すると、冗長な分岐が発生する;対称性破壊制約を追加すること。
よくある質問
決定版整数計画法と確率的整数計画法の違いは何ですか?
決定版IPでは、全ての目的関数および制約パラメータは固定かつ既知である。確率的IPは、確率分布またはシナリオを通じて不確実なパラメータを明示的にモデル化し、それらのシナリオ全体でロバストまたは期待値として最適となる解を生成する。決定版IPはより単純で解くのが速いが、不確実性を無視する。
二値計画法は整数計画法の特殊なケースですか?
はい。二値(0-1)計画法は、各決定変数を{0, 1}に制限する。これは最も一般的な特殊ケースであり、施設を開設するかどうか、プロジェクトを選択するかどうか、作業員を割り当てるかどうかといったYes/Noの決定に使用される。一般的な整数計画法は、任意の非負整数値を許容する。
いつ決定版IPからヒューリスティック手法に切り替えるべきですか?
分岐限定木が許容可能な時間制限内で探索するには大きすぎる場合、および優れたヒューリスティック(遺伝的アルゴリズム、焼きなまし法、大規模近傍探索)からの最適性ギャップがアプリケーションで許容できる場合。厳密な最適化から逸脱する場合は、ギャップを報告し正当化すること。
決定版IPは非線形目的関数または制約を扱えますか?
古典的な決定版IPは線形性(整数線形計画法)を仮定する。非線形整数計画法は存在するが、実質的に困難である。多くの非線形形式は、補助的な二値変数とビッグM再定式化を通じて線形化できる。二次整数計画法(QIP)は、一部の現代ソルバーによって直接サポートされている。
実際には決定版IPにどのソルバーを使用すべきですか?
商用:最高のパフォーマンスのためにはGurobiまたはIBM CPLEX。学術/オープンソース:SCIP、CBC(COIN-OR経由)、またはHiGHS。全て分岐カット法を自動前処理で実装している。Pythonユーザーの場合、PuLP、Pyomo、またはscipy.optimize.milpが便利なモデリングインターフェースを提供する。
関連する手法
参考文献
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
DOI 文献を開くコピーしました。Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN:9780471283669コピーしました。