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

混合整数線形計画法

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

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

決定変数が連続変数及び離散変数で、制約条件や目的関数が全て線形の式で表現された 数理計画問題を混合整数線形計画問題と呼びます。

線形の式とは、変数の 1 次式で記述してある式を指します。 線形計画問題の例に対して変数 x が整数変数だとすると、 右の図のイメージになります。 x は連続的に全ての値を取れるわけではないので、 右の図の濃い青の部分(厳密には横幅はありませんが)が全ての制約条件及び離散制約 を満たす実行可能領域になります。このように見ると、実行可能領域自体は小さくなり そうなので探索が楽なように感じるかもしれませんが、問題自体は非常に難しくなります。

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

アルゴリズムイメージ

線形計画問題に対して難しくなる理由は 2 つです。一つは凸多面体の頂点に最適解がある という性質がなくなりますので、単体法のようなアプローチができなくなること。もう一つ は離散変数を扱うので微分が不可能になり、内点法のようなアプローチができないことです。 アルゴリズムの発想の出発点としては、上記の問題であれば、x が 0, 1, 2, 3, 4, 5 のときの 最適解( x を固定して連続変数 y のみに関して解いた結果)を全て求めて比較すれば最適解が出せるという ことになります。

この方法だと、結局離散変数の全通り探索が必要になるので非常に計算速度が遅いです。 右のイメージ図のように、全通り探索しなくてよいようにツリー構造の途中のノード以下を カットする手法、分枝限定法が主流になっています。

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

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

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

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

実行可能解とは、最適解かどうかは分からないが、とりあえず制約式は(整数条件も!)満たしている解のことです。分枝限定法の高速化の鍵は、良い実行可能解をできるだけ早く見つけることにあります。Numerical Optimizer は,丸め・局所探索などのヒューリスティクスを独自の方法で行い、実行可能解を早く見つける工夫を行っております。

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

この他にも、前処理・分枝する変数の選択などで様々な工夫を行い、高速化を行っています。