整数計画法 — IPおよび混合整数計画法 (MIP)
- 提唱者
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- 年
- 1958
- 種類
- Mathematical optimisation — exact combinatorial method
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
整数計画法(IP)、一部の変数が整数に制限される場合は混合整数計画法(MIP)とも呼ばれる、は、一部または全ての決定変数が整数値またはバイナリ値を取る必要がある数理最適化の一分野である。線形計画法を基盤とし、Ralph Gomoryの切除平面法(1958年)およびLandとDoigの分枝限定法アルゴリズム(1960年)を通じて形式化され、以来、スケジューリング、割り当て、ルーティング、およびリソース配分の問題に対する標準的な厳密解法フレームワークとなっている。
手法の背後にある直感
通常の線形計画法は、連続的な実行可能領域内の最良点を見つける。しかし、多くの現実の決定は離散的である――看護師を2.7人配置したり、倉庫を半分開いたりすることはできない。整数計画法は、一部または全ての変数が整数(またはバイナリの0/1選択)でなければならないという制約を追加する。その制約の代償は計算コストである。実行可能集合はもはや滑らかな表面ではなく、散在する点の集合となり、最良点を見つけるには膨大な数の候補解を調べる必要があるかもしれない。ソルバーは、問題をより小さなサブ問題にインテリジェントに分割(分枝)し、これまでに見つかった最良解よりも悪い枝を刈り込み(限定)、同時に不等式(切除平面)を追加して連続近似を強化することで、これを管理する。
歴史学
整数計画法は、研究者が線形計画法を離散的決定に拡張しようとした1950年代後半に登場した。Ralph Gomoryは1958年に体系的な切除平面法を導入し、有限個のカットを追加することで原理的には任意の整数計画問題を解くことができることを証明した。LandとDoig(1960年)は分枝限定法を形式化し、これが支配的な厳密解法アルゴリズムとなった。Wolsey(1998年)およびNemhauserとWolsey(1988年)は、この分野が依然として依存している標準的な教科書的解説を提供した。実用的な革命は、両技術と高度なヒューリスティックを組み合わせた分枝カット法ソルバーの開発(1990年代)と、その後の大規模な実世界アプリケーションを可能にする商用およびオープンソースソルバーの性能爆発によってもたらされた。
使うべき場面
決定が本質的に離散的(バイナリのYes/No選択、整数数量、または論理的なOn/Off制約)であり、かつ証明可能な品質境界を持つ厳密またはほぼ厳密な最適解が必要な場合に、整数計画法を使用する。スケジューリング、乗務員およびリソース割り当て、車両ルーティング、施設配置、資本予算、ポートフォリオ選択に適している。IPは統計的推論手順ではなく決定論的最適化フレームワークであるため、最小サンプルサイズ要件はない。変数の型はバイナリ、カテゴリカル(バイナリとしてエンコード)、または連続(混合整数の場合)が可能である。主な実用的な要件は、問題が線形目的関数と線形制約でモデル化できることである。目的関数または制約が非線形の場合は、混合整数非線形計画法(MINLP)の拡張が必要となる。
限界と注意点
- 整数計画法は一般にNP困難であり、求解時間は問題サイズと共に指数関数的に増加する可能性があり、定式化が悪いと問題が悪化する。
- 弱いLP緩和(大きな整数性ギャップ)は、深い、コストのかかる探索木と長い実行時間につながる。
- 大規模カテゴリカル変数のバイナリ展開は、モデルサイズを爆発させる可能性がある。
- 非常に大規模なインスタンスでは、ソルバーはゼロギャップを達成するのではなく、ギャップ許容誤差を指定して早期に終了する必要がある場合がある。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- ヒューリスティックとは異なり、品質保証を提供しないものとは対照的に、厳密な最適解を証明された最適性ギャップと共に生成する。
- 組み合わせ決定のための自然なフレームワークとなる、バイナリ変数および一般整数変数をネイティブに処理する。
- 同じ数学的機構を用いて、スケジューリング、ルーティング、割り当て、ナップサック問題など、幅広い領域の問題に適用可能である。
- 現代の分枝カット法ソルバーは、数十年前には解けなかった数百万の変数と制約を持つ問題を解くことができる。
応用
- スタッフおよび看護師のスケジューリング――勤務時間規制を尊重しつつ、人員配置要件を満たすシフトの割り当て。
- 車両ルーティングとロジスティクス――容量および時間窓の制約の下での最小コスト配送ルートの発見。
- 施設配置――総流通コストを最小化するために、どの倉庫または工場を開設するかを決定する。
- 資本予算――予算内で投資プロジェクトのポートフォリオを選択し、総収益を最大化する。
- 生産計画――セットアップコストと保管コストのバランスをとるために、期間にわたる整数ロットサイズの決定。
- ネットワーク設計――通信または輸送ネットワークにどのリンクを設置するかを選択する。
使い方
使い方
問題は数理計画問題として定式化される。すなわち、決定変数(問題が要求する場合には整数またはバイナリとして宣言されなければならない)を定義し、最小化または最大化する線形目的関数を記述し、全ての線形制約を列挙する。タイトな定式化――その連続(LP)緩和が真の整数最適値に可能な限り近いもの――は、求解時間を劇的に短縮する。
緩和されたLPを解くことは高速であり、境界値を提供する。その最適値は常に真の整数最適値以上である(最小化問題に対する下界)。緩和解が偶然にも全て整数であれば、問題は解決される。そうでなければ、緩和と整数性の間のギャップが探索を導く。
緩和解における分数値変数が選択され、問題は2つのサブ問題に分割される――一方はその変数を切り捨て、他方は切り上げることを要求する。各サブ問題はそれ自体で緩和され、解かれ、探索木が作成される。その緩和境界がこれまでに見つかった最良整数解よりも悪い枝は、さらなる探索なしに刈り込まれる。
切除平面は、整数実行可能点を一切除去することなく、LP緩和実行可能領域の一部を切り捨てる有効な線形不等式である。強力なカット(Gomoryカット、被覆不等式、クリークカット)を追加すると、LP境界がタイトになり、ソルバーが探索する必要のあるノード数が減少する。
探索された全てのノードにわたる最良の整数実行可能解が最適解として返される。最適性ギャップ――最良整数解と最良の残りの境界値とのパーセンテージ差――が報告される。ギャップがゼロであれば、大域的最適性が保証される。大規模なNP困難なインスタンスでは、ソルバーはユーザー指定のギャップ許容誤差で早期に終了し、証明可能な境界を持つほぼ最適解を返すことがある。
よくある落とし穴
- 本来整数であるべき変数を連続として宣言したり、その逆を行ったりすると、サイレントに誤った解が生成される。常に変数型が問題の物理的現実と一致しているか確認すること。
- 大きなLP緩和ギャップを持つ緩い定式化は、過度の分枝を引き起こす。求解前に、定式化のタイト化(強力な不等式、対称性破壊)に時間を投資すること。
- ソルバー出力における整数性ギャップの無視。報告された目的値は、ギャップがゼロでない限り、大域的最適値とは限らない、見つかった最良の整数解にすぎない。
- 目的関数または制約が非線形である問題に、適切なMINLP処理なしでIPを適用すると、不正確なモデルが得られる。
- スケジューリングまたはルーティング問題において、有効な不等式(クリークカットや被覆カットなど)を追加しないと、かなりのパフォーマンス向上の機会を逃すことになる。
よくある質問
IPとMIPの違いは何ですか?
純粋な整数計画法(IP)では、全ての決定変数が整数でなければならない。混合整数計画法(MIP)では、一部の変数は整数またはバイナリであるが、他の変数は連続であることが許容される。MIPは、ほとんどの実問題が離散的な選択と連続的な数量を混合するため、実用上より一般的でより広く使用されているフレームワークである。
線形計画法が多項式時間で解けるのに、なぜ整数計画法はNP困難なのですか?
線形計画法は凸多面体上で最適化を行い、シンプレックス法または内点法によって多項式時間で解くことができる。整数性制約を追加すると、この凸性が破壊される。実行可能集合は有限であるが、潜在的に天文学的に大きい整数点の集合となり、一般に最良点を見つけるための多項式時間アルゴリズムは知られていない。LP緩和は境界を提供するが、直接的な解ではない。
私の解が最適であるかどうかはどうすればわかりますか?
ソルバーは最適性ギャップ――見つかった最良整数解と残りの最良下界とのパーセンテージ差――を報告する。0%のギャップは、大域的最適性を証明する。大規模問題では、ギャップ許容誤差(例:1%)を設定し、ほぼ最適解を受け入れることができる。その境界は、真の最適値がそのパーセンテージよりも良くならないことを保証する。
「タイトな」定式化とは何であり、なぜそれが重要なのですか?
タイトな定式化とは、そのLP緩和が整数最適値に近い境界を与え、小さな整数性ギャップを残すものを指す。ギャップが小さい場合、分枝限定法はより少ないノードを探索する必要があり、より速く終了する。Gomoryカット、被覆不等式、またはクリークカットなどの有効な不等式を追加すると、定式化がタイトになり、ソルバーの高速化に最も影響を与えることが多い。
関連する手法
参考文献
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN:9780471283669コピーしました。Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN:9780471359432コピーしました。