トップ > 最適化とは > 線形計画法

線形計画法

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

線形計画問題とは

決定変数が連続変数で、制約条件や目的関数が全て線形の式で表現された数理計画問題を 線形計画問題と呼びます。 線形の式とは、変数の 1 次式で記述してある式を指します。

例えば右のグラフのようなイメージになります。 右のグラフは 2 変数( x ,y )で制約式が 3 つの最適化問題をグラフ化 したものになります。3 つの制約式を満たす範囲は水色部分(実行可能領域)になり、 そのどこかが最適解ということになります。線形計画問題は実行可能領域が凸多面体になり 、最適解はその頂点のいずれかになることが知られています。右の例では目的関数に触れて いませんが、目的関数がどんな形状であっても(線形である必要はありますが)赤い○で囲った 頂点のいずれかになります。

線形計画問題イメージ

アルゴリズムイメージ

単体法

単体法はイメージとしては凸多面体である実行可能領域の頂点を探索する アルゴリズムになります。単体法は数理計画法の歴史の中で最も古いアルゴリズム で、数理計画法の誕生と共に産声を上げました。単体法についてはメールマガジンの バックナンバー 「数理計画法の誕生と発展」 をご覧ください。

単体法イメージ

内点法

内点法は凸多面体である実行可能領域の内部を探索するアルゴリズムになります。 直感的には表面を探索するよりは近道が出来そうですので、単体法に比べて高速な アルゴリズムのように感じられるかも知れませんが、実際のところは問題によって そうとは言い切れません。詳しくはメールマガジンのバックナンバー 「新・線形計画法 内点法 VS 単体法」 をご覧ください。

単体法イメージ

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

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

単体法

単体法アルゴリズムの理論は既に成熟しておりますが、プログラムとして実装するに当たり 性能を左右する工夫が数多くある事は、実はあまり知られていません。

代表的なものを幾つか紹介しましょう。

例えば一般の数理計画法の教科書では、最初の実行可能基底解を得るために ビッグ M 法がよく紹介されますが、この方法では高速・安定に実行可能基底解を 得る事はできません。また、実行可能基底解から別の実行可能基底解に移動する 際には、相対コスト係数を見る流儀・実際の減少量を見る流儀など複数のアイデアが 存在し、これらをうまく調整する必要があります。さらに、内部の行列データの 保持方法を工夫する事により、計算量を格段に圧縮する事ができます。

この他にも様々な工夫がありますが、これら一つ一つを丁寧に組み込む事で、 Numerical Optimizer の単体法は高い性能を誇っています。

内点法

線形計画問題に対する内点法は、大きく分けて「主内点法」「主双対内点法」の二種類が 存在します。前者の方が歴史がありますが、実用上優れているのは後者の「主双対内点法」 だとの見方が一般的です。「主双対内点法」の中にも様々な流派がありますが Numerical Optimizer で 採用しているアルゴリズムの大枠は「予測子・修正子法」と呼ばれる方法です。

ただし Numerical Optimizer では単に「予測子・修正子法」をそのまま適用している訳ではありません。 主双対内点法の理論において、収束性を保証する生命線とも言える、バリアパラメータの更新 ルールは独自の方法を採用しています。理論上優れた更新ルールは、求解速度の観点からは 必ずしもベストな選択肢ではありません。

また、内点法において最も計算時間を要する、疎対称連立一次方程式の計算ロジックに 関しては多数の独自工夫が凝らされています。例えば Bunch-Parlett 分解と呼ばれる方法 を適用する事により、内部で自由変数を分解する事無く、そのまま取り扱う事ができます。

さらに、問題のスケーリング変換や、初期値の設定も高速性・安定性に大きく影響します。 スケール差が大きな問題や、境界領域近くの初期値設定がまずい事は良く知られていますが、 それ以外の性質に関しては殆ど公には知られていないと言って良いでしょう。 これらの問題についても、 Numerical Optimizer の内点法には現実の問題に対して培ったノウハウが 凝縮されています。