2. 定式化の複雑さ#
2.1. 説明#
数理最適化モデルが実際の求解を前提とした場合に， どれだけの求解時間を要する難易度をもった複雑さを有しているかは定式化で重要な観点になる．
定式化の複雑さはおよそ次の分類でおおまかに判断される．
線形・非線形の違い
非線形の中でも，凸・非凸の違い
整数変数の数
より単純な構造に定式化できると，それだけ求解時間を短縮できるため， 例えば「非線形を線形で定式化できた．」とか「非線形な問題だが凸で定式化できる．」などということには大きな意義がある．
2.1.1. 線形か非線形か#
考える問題の「変数」「制約条件」「目的関数」が判明すれば， 数理最適化モデルとして定式化すること自体はそれほど難しいことではない． そして現実的な世界は非線形な現象・規則で溢れており，ありのままに定式化を図ると非線形な定式化となりやすい．
数理最適化のソルバーに限らず，数多の数値計算ソフトウェアでは，非線形な最適化問題をサポートしている． しかしそのことと求解時間や計算資源の規模が現実的な範囲に収まるかは別問題である． 基本的に非線形問題は非常に難しく，変数の数が数百数千は全く現実的ではない．
このため 計算機での求解を前提とする場合に，非線形な定式化を線形な定式化に帰着させることは， 避けて通ることができないほどの重要な観点 になっている．
線形な定式化への帰着には完全に等価な定式化に書き換えるものもあれば， 近似的な定式化に書き換える場合もある．
重要
特に「近似的な定式化への書き換え」は問題の個別の事情に大きく依存するため，どこを近似すればよいかという業務理解が必須になってくる． また同時に「近似したい」という背景が 消極的な意味ではない ということを求解結果の利用者が認識して，運用面で調整を図ることも重要になってくることもある．
2.1.2. 非線形でも凸か非凸か#
一般の非線形問題は非常に難しい問題だが，その中でも変数がすべて実数で凸な問題ならば， およそ数万変数もの規模まで対応が可能になってくる．
そのような問題クラスの代表例とは 二次最適化問題 であり， QP (Quadratic Programming Problem) と略称される問題である．
QP として定式化できる問題としては「最小二乗問題」「ポートフォリオ最適化問題」などがある．
2.1.3. 整数変数の数#
変数には大別して実数変数と整数変数の二種があり，整数変数を用いた定式化の方が難しい． この難易度の差の理由には幾つかあるが，例えば実数変数の場合には微分が可能で傾きの情報を取得して最適解の探索が行えるのに対して， 整数変数の場合にはそれができず，組み合わせを検討する必要があるという側面がある．
制約条件式と目的関数が何れも線形に書けていた場合でも， このような難易度を背景に更に変数の種別に応じた次表の分類がある．
変数の種別 |
問題分類名称 |
問題分類略称 |
問題規模 |
|---|---|---|---|
実数変数のみ |
数十万変数 |
||
実数変数と整数変数の混合 |
問題・定式化依存 |
||
整数変数のみ |
問題・定式化依存 |
最も望ましい定式は LP に分類される定式化であり，対応可能な問題規模の見積もりはそれほど間違えることはない． またこの問題規模は今後のハードおよびソフトウェアの技術進展によって増えていく． このような主旨は次に引用するように，例えば「10 年前には解くのに 1 年を要した計算が 30 秒で解けるようになるといったことが起こり得て， その進展に応じて相手にできる問題が増えていくことになる．」というようにしばしば言及される事柄である．
Three orders of magnitude in machine speed and three orders of magnitude in algorithmic speed add up to six orders of magnitude in solving power: A model that might have taken a year to solve 10 years ago can now solve in less than 30 seconds. Ofcourse, no one waits one year to solve a model, at least no one I know. The real meaning of such an advance is much harder to measure in practice, but it is real nevertheless. There is no doubt that we now have optimization engines at our disposal that dwarf what was available only a few years ago, making possible the solution of real-world models once considered intractable, and opening up whole new domains of application.
一方で MIP や IP については問題規模の凡その目安はあるものの，これらはすべて問題・定式化依存であり， テストケースを用意して傾向を見る作業が必須となる．
また特に IP の場合には求解アルゴリズムとして WCSP タブーサーチあるいは WLS を用いることできる． WCSP とは変数が全て 離散変数 の場合に用いることが可能なメタヒューリスティクスアルゴリズムで， 解の最適性の保証はないが，実行可能解を得るという目的では (一概には言えないが目安として) 十数万程度の変数まで対応可能となってくる． このように問題の難易度が上がるに連れて，最適解だけでなく品質の良い実行可能解を得るということも実務上では重要な観点となってくる．