トップ > 最適化とは > 整数計画法

整数計画法

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

整数計画問題とは

一般に整数計画問題といった場合に、連続変数を含むこともありますがここでは全て離散変数であるような 問題のこととして取り扱います。連続変数を含む問題は 混合整数線形計画問題を参照ください。 線形計画問題のところで上げた例題に対して、x と y が共に整数変数という制限を加えたものが、 整数計画問題になります。右のイメージ図で濃い青色の格子点が実行可能な解候補になり、 この中のどれかが最適解ということになります。

整数計画問題イメージ

アルゴリズムイメージ

混合整数線形計画問題で紹介した分枝限定法もこの問題に適応することは可能です。 ここでは、全て離散変数の問題に適応できるメタヒューリスティクスアルゴリズム WCSP についてご紹介します。

WCSP イメージ

アルゴリズムはシンプルで、上の図のようにまず初期点から出発しその周辺(近傍)の中で一番 よい解を次の解に選択します(改善解)。これを徹底的に繰り返すことによって、解を更新していく という手法です。この方法は近似解法と呼ばれており、最適性の保証が無いながら大規模な問題に 対して、非常に有効なアルゴリズムです。

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

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

メタヒューリスティクスアルゴリズムの長所として、大規模問題 に対し高速に解が得られることがあげられます。 一方、必ずしも大域的最適性を保証できない、という短所があります。

そのため、Numerical Optimizer に搭載されている WCSP アルゴリズムは汎用性を 考慮して タブーサーチ を採用し、その短所を補っています。 また、制約に対する重みを動的に変更し、探索方向を効率良くす る工夫や、局所解から出られない場合に近傍を動的に拡大する等、 多くの実装上の工夫が組み込まれています。

Numerical Optimizer が搭載している WCSP アルゴリズムは「京都大学・問題解決エンジンプロジェ クト」により生み出されたものです。Numerical Optimizer には独自の差分評 価テクニックが導入され、さらなる高速化を実現しています。

当然この WCSP アルゴリズムも Numerical Optimizer に付属のモデリング言語 SIMPLE を用いて 利用することができ、 一つのモデルファイルで分枝限定法と切り替えて利用することも可能です。 また、様々な組み込み関数(Selection/min/max/argMin/argMax…) を用意しておりモデリングの自由度とパフォーマンスの向上を実現しています。

その他にも求解設定(初期解生成の乱数やイテレーションを制限) に関する wcsp 特有のオプションが備わっています。 オプションの指定によりシフトスケジューリングなど 複数のシフト提案が必要な場合にも対応することができます。