トップ > 最適化とは > 混合整数線形計画法

混合整数線形計画法

ここでは数理計画法の中の混合整数線形計画法についてご紹介します。 混合整数線形計画法とは混合整数線形計画問題を解く解法・アルゴリズムを総称したものです。 なお Numerical Optimizer の「LP/IP Lite」「LP/IP」「NLP」「フルセット」のモジュールが 混合整数線形計画法のアルゴリズムに対応しています。

混合整数線形計画問題とは

決定変数の一部が整数変数でなければならないという制約を持つ、 線形計画問題を混合整数線形計画問題と呼びます。

線形計画問題の例に対して変数 x が整数変数だとすると、 実行可能領域(制約条件を満たす領域)は右の図のイメージになります。 x は連続的に全ての値を取れるわけではないので、 右の図の濃い青の部分 (厳密には横幅はありませんが)になっています。

小さな例でこのように見ると、実行可能領域自体は小さくなりそうなので探索が楽なように感じるかもしれませんが、 問題は非常に難しくなります。

混合整数線形計画問題イメージ

アルゴリズムイメージ

線形計画問題に対して難しくなる理由は 2 つです。 一つは凸多面体の頂点を探せばよいわけではなくなるので、単体法のようなアプローチができなくなることです。 もう一つは離散変数が現れるので、内点法のように「解に近い方向」を微分によって求めるということもできなくなることです。

そんなわけでアルゴリズムの発想の出発点としては非常に素朴な方法である、全探索から出発せざるを得ません。 上記の問題であれば、x が 0, 1, 2, 3, 4, 5 のときの最適解 (x を固定して連続変数 y のみに関して解いた結果)を全て求めて比較するというものです。

容易に想像できることですが、この方法だと、結局離散変数の全通り探索が必要になるので大規模問題を現実的な速度で解くことができません。 そこで下のイメージ図のように、全通り探索しなくてよいように、探索の途中で得られる情報を使いながらツリー構造の途中のノード以下を計算の対象から除外(限定)する手法、分枝限定法が主流になっています。

混合整数線形計画問題イメージ

混合整数線形計画法で取り扱うことのできる応用問題

Numerical Optimizer におけるアルゴリズムの工夫

分枝限定法において計算するノードを限定する際、具体的には二つの情報を使っています。 一つは得られている実行可能解の情報、もう一つは連続緩和問題の解の情報です。

実行可能解とは、最適解かどうかは分からないが、とりあえず制約条件は(整数性の条件も!)満たしている解のことです。 連続緩和問題の解は整数性の条件を外した問題の解で、目的関数値は必ず元の問題より良くて当り前です。 ある探索ノードで連続緩和問題の解が実行可能解に負けてしまっていれば、 そのノードから派生するノードを調べても最適解は得られないことが明らかなので、 探索の範囲から外してもよい。 これが限定操作です。

分枝限定法の高速化の鍵の一つは、良い実行可能解をできるだけ早く見つけることにあります。 しかしながら、連続緩和問題の解は単体法を使えば必ず得られる一方で、 良い実行可能解を得る方法には定まったやり方がありません。 Numerical Optimizer は、丸め・局所探索などのヒューリスティクスを独自の方法で行い、 良い実行可能解を速く求める工夫を行っています。

この実行可能解探索に特化した方法が整数計画法で解説しているメタヒューリスティクスアルゴリズムです。

連続緩和問題の作り方にも工夫の余地があって、 ただ整数性の条件を外すだけでは緩和問題の解が元の問題の性質を失って、 全く限定操作の役に立たない場合があります。

Numerical Optimizer は、与えられた問題から「妥当不等式」という人工的な制約条件を推定し、 これを加えることによって緩和問題の解を改善しています。 この妥当不等式は、Gomory カットなどが知られていますが、 教科書通りに実装しても往々にして高速化は望めません。 例えば、Gomory カットは理論的には常に緩和問題の解を良くすることが知られていますが、 数値的性質が悪く単純に加えると元の問題を解きづらい形にしてしまいます。 Numerical Optimizer は実務的な問題で効果がでるよう、こうした妥当不等式に工夫を施しております。

高速化のもう一つの鍵は分枝限定法にかける前の定式化の前処理です。 整数変数の値の設定の組みあわせを実地にチェックしてみると、 論理的帰結によりすべての値の組みあわせが許されるわけではなく、 特定の組みあわせしか許されないことがわかります。 この操作を probing と呼び、ここから新たな制約を推論して、 変数の固定や、「妥当不等式」の作成といったことが可能です。 極端なケースでは、probing だけで解が一意に決定してしまう場合も存在します。 Numerical Optimizer ではこの probing を始めとする前処理の工夫を行って、分枝限定法の負担を軽減しています。