アルゴリズム
- Numerical Optimizer が解ける問題の範囲を教えてください。
- 大域的最適解は求まりますか？
- 「 tipm 」と「 trust 」の違いは何ですか？
- どの程度の大規模問題が解けますか？
- モジュール別に対応可能な問題の種類と規模を教えてください。
- 最適解が Numerical Optimizer と他ソルバーで異なっています。
- 「IPM iteration limit exceeded」と出たとき、得られた解は制約を全て満たしているのでしょうか。
- WCSP とは何ですか？
Numerical Optimizer が解ける問題の範囲を教えてください。
以下が Numerical Optimizer が適用可能な数理計画問題の種類とアルゴリズムです。
- 線形計画問題（目的関数と制約式が線形）
- 単体法・内点法（高次オーダー法）
- 二次計画問題（制約式が線形、目的関数が二次式）
- 有効制約法・内点法（直線探索法）
- 混合整数線形計画問題（線形計画法の変数が一部整数）
- 分枝限定法（単体法）
- 混合整数二次計画問題（二次計画法の変数の一部整数）
- 分枝限定法（有効制約法）
- 非線形計画問題（目的関数と制約式がすべて非線形な式）
- 内点法（信頼領域法）・逐次二次計画法
- 半正定値計画問題（行列の半正定値性に関する制約を含む）
- 内点法＜Numerical Optimizer V10 より適用可能＞
- 離散変数モデル（離散変数のみを含む問題）
- WCSP（タブーサーチに基づく制約充足アルゴリズム）
- RCPSP（資源制約つきスケジューリング問題）
- RCPSP（タブーサーチに基づくアルゴリズム）
- 目的関数の微分の情報を利用することが出来ないモデル
- DFO（derivative free optimization の手法に基づくアルゴリズム）＜有償・Numerical Optimizer V11 より適用可能＞
単一のソフトウェアでこのように広い範囲の手法をカバーしているのが Numerical Optimizer の特徴です。ただし、汎用パッケージであるため特定の問題に特化したアルゴリズムについては特別仕様による作り込みとなります。また、非線形整数計画問題については、メタヒューリスティクスアルゴリズムである WCSP や 大域的最適化アルゴリズム（有償）が適用できます。なお、WCSP/RCPSP に関して、「タブーサーチ」は焼きなまし法や遺伝的アルゴリズムなどと同列のメタヒューリスティクスアルゴリズムですが、高い汎用性を備えています。
大域的最適解は求まりますか？
一般の非線形計画問題や一部の二次計画問題は局所解の一意性が保証できません。この場合、通常の Numerical Optimizer のアルゴリズムは局所解のいずれか一つを求めるというものであるため、大域的な最適解は求まりません。初期値を振ってみる、あるいは、適当な制約式を追加するなど問題に特化した処理が必要になります。
しかし、有償アドオンである Numerical Optimizer/Global を導入することにより、一般の小規模非線形モデルの大域的最適解を求めることができるようになります。詳細については Numerical Optimizer/Global をご覧いただくか、nuopt-info@msi.co.jp までお問い合わせください。
「 tipm 」と「 trust 」の違いは何ですか？
Numerical Optimizer に搭載されている内点法のアルゴリズムである tipm と trust の異なる点は、「探索方向を決める」という手順において用いられるメリット関数と呼ばれる関数の構造が異なっていることです。どちらのアルゴリズムが有効かは問題に依存し、一概には言えません。
どの程度の大規模問題が解けますか？
以下に Numerical Optimizer バージョン 12.1.0 のベンチマーク結果より、制約式あるいは変数の数が 1 万を越えるものを抜粋したリストを掲載します。問題は全て線形計画問題です。
| 問題 | #制約式 | #変数 | #非零要素 | 計算時間(秒) |
| LP1 | 201156 | 383927 | 1053564 | 56.67 |
| LP2 | 35511 | 32734 | 220748 | 22.25 |
| LP3 | 132021 | 161692 | 1868865 | 31.69 |
| LP4 | 58867 | 8052 | 265975 | 32.44 |
| LP5 | 139758 | 283250 | 2408585 | 94.98 |
| LP6 | 66186 | 157496 | 529317 | 21.84 |
| LP7 | 246078 | 308634 | 902275 | 18.08 |
| LP8 | 105128 | 154699 | 512719 | 24.84 |
| LP9 | 2959 | 13434 | 78994 | 14.66 |
| LP10 | 23004 | 14981 | 686396 | 113.97 |
| LP11 | 74 | 123409 | 1028319 | 18.24 |
| LP12 | 10281 | 232966 | 1630758 | 21.44 |
- CPU:Intel Core(TM)2 Duo E8400 3.00Gz
- メモリ:2GB
他の大規模数理計画法パッケージと同様、Numerical Optimizer は係数行列の疎行列性を利用した実装によって高速化を実現しているため、問題を解く速度は変数や制約式の数のほか、非零要素の数、あるいは係数行列の非零要素のパターンに依存します。
そのため、計算時間について正確な見積りは難しくなります。LP7、LP8 に比べ LP5 が計算時間を所要しているのは、係数行列の非零要素数が多いためです。
メモリ所要量についても計算時間と同様の理由により正確に見積るのは難しいのですが、例えば LP7 に関しては、求解中のプロセスサイズは 233MB ですので、0.5 〜 1G バイトのメモリがあれば、メモリスワップを起こすことなく高速に計算が可能だと考えられます。
モジュール別に対応可能な問題の種類と規模を教えてください。
対応可能な問題規模（制約式数、実数変数数、整数変数数）についてはソフトウェア上の制限は設けていませんが、実際にはハードウェア性能に依存します。
また、対応可能な問題規模は問題の種類や内容にも大きく依存します。そのため、はっきりした線引きをすることは難しいのですが、下記情報をガイドラインとしてご利用ください。
- 線形計画問題（対応モジュール：全モジュール）
- 数十万の実数変数に対応可能です。
- 混合整数線形計画問題（対応モジュール：全モジュール）
- 問題内容に大きく依存します。問題の種類によっては実数変数、整数変数合わせて数万程度まで対応可能な場合があります。
- 非線形計画問題（対応モジュール：NLP モジュール、フルセット）
- 変数が全て実数の二次計画問題であれば数万変数まで対応可能です。それ以外の場合は問題内容に大きく依存します。
- wcsp （対応モジュール：LP/IP モジュール、フルセット）
- wcsp とは変数が全て離散変数の場合に用いることが可能なメタヒューリスティクスアルゴリズムです。そのため、解の最適性の保障はありませんが、十数万程度の変数まで対応可能です。
制約式数については、その複雑さに大きく依存します。そのため、ガイドラインをお伝えすることは難しいのですが、制約式の数がボトルネックとなるようなことは稀です。
最適解が Numerical Optimizer と他ソルバーで異なっています。
数理計画問題では、最適解が複数存在することがあります。最適化ソルバーが求めるのは最適解のうちの一つなので、Numerical Optimizer と他ソルバーで求められる最適解が異なることがあります。
「IPM iteration limit exceeded」と出たとき、得られた解は制約を全て満たしているのでしょうか。
解が制約を満たしている保証はありません。しかしながらユーザ側でチェックする手段があります。標準出力に
CONSTRAINT_INFEASIBILITY 7.566995919e-010
と表示されるのが「制約の違反量の合計」で、チェックの目安になります。なお内点法はその性質上、変数の上下限制約は必ず満たします。
WCSP とは何ですか？
Numerical Optimizer に搭載されているアルゴリズム WCSP は、変数が全て整数であるような離散計画問題を対象とした近似解法のアルゴリズムです。割当て問題などの実務的な大規模離散計画問題に対して高速に、準最適な実行可能解（制約を満足する解）を発見できます。