混合整数計画法 — 連続変数と整数変数の両方を含む決定に対する厳密な最適化
- 提唱者
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- 年
- 1958–1960
- 種類
- Mathematical optimization
- 系統
- Simulation / optimization
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
混合整数計画法(MIP)は、一部の決定変数が整数値を取る必要があり、他の変数は連続値を取りうる数学的最適化フレームワークである。これは線形計画法を一般化したものであり、オペレーションズ・リサーチ、ロジスティクス、スケジューリング、資源配分、工学設計など、不可分性制約(例:はい/いいえの決定や整数単位の数量)が自然に生じる分野で広く利用されている。
手法の背後にある直感
多くの現実的な最適化問題では、分割できない決定が含まれる。例えば、施設を開設するかしないか、シフトに正確に1人の作業員を割り当てるか、整数単位で発注するかなどである。連続線形計画法はこれらの現実を無視し、実装不可能な分数解を生成する可能性がある。MIPはモデル内で直接、整数性を強制する。ソルバーは、ブランチ・アンド・バウンド法を用いて、実行可能な整数解の空間を系統的に探索する。すなわち、各領域で可能な最良の解を境界付けるために緩和された連続部分問題を解き、現在見つかっている最良の整数解よりも改善できない領域を破棄し、探索をタイトにするためにカット平面を追加する。その結果、証明可能な最適解またはそれに近い解が得られる。
歴史学
整数計画法の基礎は、1958年にカット平面法を導入したRalph Gomoryと、1960年にブランチ・アンド・バウンド法を形式化したLandとDoigによって築かれた。その後の数十年で、LP緩和理論、多面体的組み合わせ論(Edmonds, Padberg, Grötschel)が発展し、1990年代までには商用ソルバーによって大規模MIPが実用的になった。この分野はNemhauser and Wolsey (1988) および Wolsey (1998) で包括的に扱われている。
使うべき場面
問題が線形または線形化可能な目的関数と制約を持ち、整数値を取る必要がある決定(施設立地、乗務員スケジューリング、資本予算、ネットワーク設計、裁断材問題など)を含む場合にMIPを使用する。証明可能な最適解またはギャップが保証された解が必要で、問題サイズが扱える範囲(現代のソルバーでは数千変数)である場合に最適な手法である。目的関数や制約が高度に非線形である場合(代わりに非線形計画法や混合整数非線形計画法を使用)、問題が厳密解法では手に負えないほど大きい場合(ヒューリスティックやメタヒューリスティックを検討)、または連続近似で十分な精度が得られる場合(速度のためにLPを使用)にはMIPを使用しない。
限界と注意点
- 最悪ケースの計算量はNP困難であり、解時間は整数変数の数とともに指数関数的に増加する可能性がある。
- 厳密な数学的定式化が必要であり、不適切に定式化されたモデルは、根本的な問題が管理可能であっても、解くことが困難になる場合がある。
- 非凸または非線形要素は、追加の線形化または特殊なソルバーを必要とし、モデルの複雑さが増す。
- 商用ツールのソルバーライセンス費用は高額になる場合があるが、高品質なオープンソースの代替策も存在する。
- 結果はモデルの質に依存する。誤った制約仕様は、意味のない最適解につながる。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 証明可能な最適解と定量化可能な最適性ギャップを生成し、厳密な意思決定の正当化を可能にする。
- バイナリ変数および一般整数変数をネイティブに扱い、現実世界の不可分性および論理制約を捉える。
- 現代のソルバー(Gurobi, CPLEX, SCIP)は、高度なブランチ・アンド・バウンド、カット平面、プリソルブを活用して、大規模インスタンスを効率的に処理する。
- 透明なモデル定式化により、仮定が明確になり、ドメイン専門家による監査が可能になる。
- 感度分析やパラメトリックスタディをサポートし、入力データに応じて解がどのように変化するかを理解できる。
- モデリング言語(AMPL, GAMS, Pyomo, JuMP)で広くサポートされており、迅速なプロトタイピングが可能になる。
応用
- サプライチェーンとロジスティクス:車両ルーティング、施設立地、整数出荷数量での在庫最適化。
- 人員配置:看護師ローテーション、乗務員割り当て、バイナリ割り当て変数でのシフト計画。
- 資本予算:予算制約下での、分割不可能な投資プロジェクトポートフォリオの選択。
- 通信およびネットワーク設計:バイナリリンク活性化決定での容量拡張とルーティング。
- エネルギーシステム:電力網におけるユニットコミットメント(各時間でどの発電機をオン/オフするかを決定)。
- 製造:製造ロットサイズ決定、機械スケジューリング、整数バッチサイズでの裁断材問題。
使い方
使い方
最適化モデルを定義する。すなわち、目的関数(最小化または最大化する決定変数の線形結合)、線形不等式および等式制約、そして整数性要件である。連続変数は分数になりうる数量を扱い、バイナリ(0/1)または一般整数変数は離散的な決定を扱う。
数式
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p整数性制約を一時的に除外して線形計画(LP)緩和問題を解く。これにより、最適MIP目的関数に対する下限値(最小化問題の場合)と、分数解となる可能性のある候補解が得られる。
数式
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0LP緩和解から分数解となった整数変数を1つ選択する。一方には床関数制約を、もう一方には天井関数制約を追加して、2つの子問題を作成する。これにより、整数解可能な点を失うことなく、実行可能空間を分割する。
数式
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil各子問題のLP緩和問題を解く。もしその下限値が、現在見つかっている最良の整数解(インカレント)よりも悪い場合は、その枝を刈り込む。もしLP解が偶然にも整数実行可能であれば、インカレントを更新して、より良い目的関数値が得られるか確認する。
数式
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}オプションとして、分数解のLP解を切り捨てるが整数実行可能な点は失わない有効な不等式であるカット平面を追加する。Gomoryカットが古典的なアプローチであるが、問題固有のカット(例:クリークカット、フローカット)はツリーサイズを劇的に削減できる。
数式
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}ブランチ・アンド・バウンドツリーが完全に探索された場合、または最良整数解と全体の下限値との間のギャップがユーザー指定の許容誤差(例:0.01%)内に収まった場合に停止する。最適性証明書とともにインカレント解を返す。
数式
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonよくある落とし穴
- 最適性ギャップの許容誤差をきつすぎると、ソルバーが無限に実行される可能性がある。常に実用的なギャップ(例:1%)を設定する。
- モデル内の対称性(例:交換可能な施設)は、冗長な枝を生み出し、探索ツリーを爆発させる。対称性破砕制約を使用する。
- 弱いLP緩和(大きな整数性ギャップ)は、非常に大きなブランチ・アンド・バウンドツリーにつながる。有効な不等式を追加したり、定式化をタイトにしたりすることに時間を投資する。
- 一部の変数のみ整数である必要があるのに、すべてを整数として扱うのは不必要にコストがかかる。論理制約で要求される場合にのみバイナリ変数を使用する。
- 良好な初期実行可能解でのウォームスタートを無視すると、最初のインカレントを見つけるためにソルバー時間を浪費する。
よくある質問
MIPと線形計画法(LP)の違いは何ですか?
LPはすべての決定変数が連続値(実数値)であることを要求し、物理的に実行不可能な分数解(例:トラック2.7台)を生成することがある。MIPは一部またはすべての変数に整数性制約を追加し、計算複雑性が増す代償として、整数またはバイナリ解を強制する。
どのような場合にヒューリスティックではなくMIPを使用すべきですか?
問題が数百万の変数を持つ場合、高度に非線形な構造を持つ場合、またはほぼリアルタイムの解が必要な場合、厳密なMIPは遅すぎる可能性がある。メタヒューリスティック(遺伝的アルゴリズム、焼きなまし法など)は迅速に良好な解を生成できるが、最適性保証はない。解の品質証明が重要な場合はMIPが好ましい。
最適性ギャップとは何ですか?また、どれくらい小さくすべきですか?
ギャップは(インカレント目的関数値 - LP下限値)/ LP下限値で、パーセンテージで表される。これは、現在知られている最良の整数解が真の最適解からどれだけ離れているかを証明する。ほとんどの実用的なアプリケーションでは0.1~1%のギャップで十分であるが、よりタイトなギャップは指数関数的に多くのソルバー時間を必要とする。
MIPは非線形目的関数や制約を扱えますか?
標準的なMIPは線形性を仮定する。非線形関係は線形化(例:区分的線形近似、積のバイナリ展開)するか、混合整数非線形計画法(MINLP)ソルバーで処理する必要があるが、これらは解くのが著しく困難である。
MIPにはどのソルバーが推奨されますか?
商用:GurobiとCPLEXが業界標準である。オープンソース:SCIP、CBC(COIN-OR経由)、HiGHSは中規模問題に対して競争力がある。すべてがAMPL、Pyomo、JuMPなどの標準モデリングインターフェースをサポートしている。
関連する手法
参考文献
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN:9780471359432コピーしました。Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN:9780471283669コピーしました。