Nuorium Optimizer FAQ
アルゴリズム
- Nuorium Optimizer が解ける問題の範囲を教えてください。
- 大域的最適解は求まりますか？
- どの程度の大規模問題が解けますか？
- 対応可能な問題の種類と規模を教えてください。
- 最適解が Nuorium Optimizer と他ソルバーで異なっています。
- 「IPM iteration limit exceeded」と出たとき、得られた解は制約を全て満たしているのでしょうか。
- wcsp タブーサーチとは何ですか？
Nuorium Optimizer が解ける問題の範囲を教えてください。
以下が Nuorium Optimizer が適用可能な数理計画問題の種類とアルゴリズムです。
- 線形計画問題（目的関数と制約式が線形）: 単体法・内点法（高次オーダー法）
- 二次計画問題（制約式が線形、目的関数が二次式）: 有効制約法・内点法（直線探索法）
- 混合整数線形計画問題（線形計画法の変数が一部整数）: 分枝限定法（単体法）
- 混合整数二次計画問題（二次計画法の変数の一部整数）: 分枝限定法（有効制約法）
- 非線形計画問題（目的関数と制約式がすべて非線形な式）: 内点法（信頼領域法）・逐次二次計画法
- 半正定値計画問題（行列の半正定値性に関する制約を含む）: 内点法＜Nuorium Optimizer V10 より適用可能＞
- 離散変数モデル（離散変数のみを含む問題）: wcsp タブーサーチ（タブーサーチに基づく制約充足アルゴリズム）、wls（重み付き局所探索法）
- WCSP（重み付き制約充足問題）: wcsp タブーサーチ、wls
- RCPSP（資源制約つきスケジューリング問題）: rcpsp タブーサーチ（タブーサーチに基づくアルゴリズム）
単一のソフトウェアでこのように広い範囲の手法をカバーしているのが Nuorium Optimizer の特徴です。ただし、汎用パッケージであるため特定の問題に特化したアルゴリズムについては特別仕様による作り込みとなります。また、非線形整数計画問題については、メタヒューリスティクスアルゴリズムである wcsp タブーサーチが適用できます。なお、wcsp タブーサーチと rcpsp タブーサーチ に関して、「タブーサーチ」は焼きなまし法や遺伝的アルゴリズムなどと同列のメタヒューリスティクスアルゴリズムですが、高い汎用性を備えています。
大域的最適解は求まりますか？
一般の非線形計画問題や一部の二次計画問題は局所解の一意性が保証できません。この場合、通常の Nuorium Optimizer のアルゴリズムは局所解のいずれか一つを求めるというものであるため、大域的な最適解は求まりません。初期値を振ってみる、あるいは、適当な制約式を追加するなど問題に特化した処理が必要になります。
どの程度の大規模問題が解けますか？
以下に Nuorium Optimizer バージョン 22.1.0 のベンチマーク結果より、制約式あるいは変数の数が 1000 - 500000 となる問題のリストを掲載します。問題は全て混合整数線形計画問題です。
| 問題 | #制約式 | #変数 | 計算時間(秒) |
|---|---|---|---|
| MILP1 | 1059 | 8165 | 1388.46 |
| MILP2 | 1161 | 1495 | 634.28 |
| MILP3 | 1737 | 1042 | 953.45 |
| MILP4 | 3117 | 1294 | 1426.77 |
| MILP5 | 3255 | 3706 | 1226.96 |
| MILP6 | 5150 | 1810 | 1145.42 |
| MILP7 | 5282 | 20347 | 594.95 |
| MILP8 | 6805 | 885 | 1130.15 |
| MILP9 | 7328 | 1204 | 1425.43 |
| MILP10 | 7350 | 2221 | 1083.91 |
| MILP11 | 7350 | 2221 | 1300.92 |
| MILP12 | 9013 | 5997 | 820.27 |
| MILP13 | 10218 | 12310 | 734.60 |
| MILP14 | 10240 | 9500 | 1382.05 |
| MILP15 | 14870 | 17657 | 552.89 |
| MILP16 | 18380 | 577 | 872.98 |
| MILP17 | 19466 | 18440 | 685.89 |
| MILP18 | 34219 | 3708 | 1330.03 |
| MILP19 | 34759 | 68343 | 599.90 |
| MILP20 | 63009 | 508 | 540.56 |
| MILP21 | 164547 | 328819 | 916.51 |
- CPU:Intel(R) Xeon(R) CPU E5-1410 v2 @ 2.80GHz
- メモリ: 32 GB
- キャッシュサイズ：10 MB
Nuorium Optimizer は係数行列の疎行列性を利用した実装によって高速化を実現しているため、問題を解く速度は変数や制約式の数のほか、非零要素の数あるいは係数行列の非零要素のパターンに依存します。また整数変数を含んだ問題は難しさが問題の規模のみに依存しないということが知られています。数十万変数でもすぐに解ける場合もあれば、数百変数でも現実的な時間内で解けない場合があり、計算時間について正確な見積りはより困難になります。
ご自身のモデルがどの程度の計算規模になるかどうかを検証するには Nuorium Optimizer の試用版を用いて検証することをおすすめします。
対応可能な問題の種類と規模を教えてください。
対応可能な問題規模（制約式数、実数変数数、整数変数数）についてはソフトウェア上の制限は設けていませんが、実際にはハードウェア性能に依存します。
また、対応可能な問題規模は問題の種類や内容にも大きく依存します。そのため、はっきりした線引きをすることは難しいのですが、下記情報をガイドラインとしてご利用ください。
- 線形計画問題: 数十万の実数変数に対応可能です。
- 混合整数線形計画問題: 問題内容に大きく依存します。問題の種類によっては実数変数、整数変数合わせて数万程度まで対応可能な場合があります。
- 非線形計画問題: 変数が全て実数の二次計画問題であれば数万変数まで対応可能です。それ以外の場合は問題内容に大きく依存します。
- 離散変数モデル: wcsp タブーサーチを用いて解くことができます。wcsp タブーサーチとは変数が全て離散変数の場合に用いることが可能なメタヒューリスティクスアルゴリズムです。そのため、解の最適性の保障はありませんが、十数万程度の変数まで対応可能です。
制約式数については、その複雑さに大きく依存します。
最適解が Nuorium Optimizer と他ソルバーで異なっています。
数理計画問題では、最適解が複数存在することがあります。最適化ソルバーが求めるのは最適解のうちの一つなので、Nuorium Optimizer と他ソルバーで求められる最適解が異なることがあります。
「IPM iteration limit exceeded」と出たとき、得られた解は制約を全て満たしているのでしょうか。
解が制約を満たしている保証はありません。しかしながらユーザ側でチェックする手段があります。標準出力に
CONSTRAINT_INFEASIBILITY 7.566995919e-010と表示されるのが「制約の違反量の合計」で、チェックの目安になります。なお内点法はその性質上、変数の上下限制約は必ず満たします。
wcsp タブーサーチとは何ですか？
Nuorium Optimizer に搭載されているアルゴリズム wcsp タブーサーチは、変数が全て整数であるような離散計画問題を対象とした近似解法のアルゴリズムです。割当問題などの実務的な大規模離散計画問題に対して高速に、準最適な実行可能解（制約を満足する解）を発見できます。
wcsp タブーサーチのアルゴリズムについては整数計画法に概要があります。