4.2 アルゴリズム一覧
Nuorium Optimizerは以下のようなアルゴリズムを備えています．見出しの解法名は，アルゴリズムを指定する際に用います．カッコ内の解法名は，標準出力にMETHODとして出力されるものです．
- simplex：単体法（SIMPLEX）
線形計画法の解法として古くから知られている方法です．大規模問題では内点法に速度的に劣りますが，可能基底解が求まり原理的に内点法/外点法よりも高精度です．
整数変数を含む問題に対して指定すると，単体法を分枝限定法（Branch and bound method）という枠組のなかで繰り返し行って，最適性の保証のある整数解を求めます．大規模問題において基底解が必要な場合には，"cross:on"と指定して内点法からのクロスオーバーを用いるのが有利です． - hsimplex：単体法(HSIMPLEX)
PySIMPLE から呼び出して使える単体法です．線形計画問題および凸二次計画問題に適用できます．simplex と比較して，よりスパース性を活用しているので，多くのケースで高速に動作します．整数変数を含んだ問題に対しては整数性を緩和した問題を解くのでご注意ください． - asqp：有効制約法（ACTIVE_SET_QP）
単体法と同様，古典的な凸二次計画問題の厳密解法です．1万変数以上の大規模問題では，一般に内点法（直線探索法（Line Search Method））に劣りますが，- 変数に比べて制約式の数が非常に少ない（1/10以下）場合
- 目的関数のヘッセ行列が密行列である場合
には内点法よりも高速かつ高精度です．また，整数計画法に対応しているので，整数変数が含まれている凸二次計画問題を解くことができます．
"cross:on"と指定することで内点法からのクロスオーバーを用いることができるので，大規模問題に対して高精度な解を求めることができます． - higher：線形計画問題専用内点法（HIGHER_ORDER）
線形計画法に特化した内点法で，大規模な線形計画問題の解法としては最も高速です．単体法と違い，可能基底解は求まりません． - lipm：直線探索法（LINE_SEARCH_IPM）
一般の凸計画問題に適用可能な内点法です．問題が凸であることがわかっている場合には信頼領域法よりも高速です．幅広い範囲の問題に対して有効です． - bfgs：準ニュートン法（BFGS_LINE_SEARCH）
準ニュートン法を用いた直線探索に基づく内点法です．ヘッセ行列の近似行列を密行列として保持します．小規模（50～500変数以下）かつ非線形性の強い問題に対してtipmよりも有効な場合があります． - tipm：信頼領域内点法（TRUST_REGION_IPM）
大規模なものを含む一般の非線形計画問題に適用可能な内点法です．幅広い範囲の問題に対して有効です． - lsqp：直線探索法に基づく逐次二次計画法（LINE_SEARCH_SQP）
準ニュートン法によって二階微係数を求める逐次二次計画法です．小規模（50～100変数以下）な非線形計画問題に適しています．
問題によっては直線探索内点法（lipm）よりも安定的により精度の良い解を導くことができます． - tsqp：信頼領域法に基づく逐次二次計画法（TRUST_REGION_SQP）
二階微係数をそのまま用いる逐次二次計画法です．大規模なものを含む一般の非線形計画問題に適用可能な方法です．一般に内点法よりも低速ですが，問題によっては内点法よりも安定的に，より精度の良い解を導くことができます．
変数の数よりも制約式数が多い場合には内点法（tipm）よりも高速な場合があります． - lsdp：線形半正定値計画問題に対する主双対内点法
線形の半正定値計画問題に対する主双対内点法です．目的関数・制約式に出現する項は線形である必要があります．内部でメリット関数の計算を行いません． - trsdp：信頼領域法を用いた非線形半正定値計画問題に対する主双対内点法
目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です．メリット関数の降下を保証するために，信頼領域法を利用しています． - wcsp：制約充足問題ソルバ（WCSP）
京都大学「問題解決エンジン」グループの開発による制約充足問題に対するアルゴリズムです．必ずしも厳密解が求まるわけではありませんが，大規模な整数計画問題に対し，非常に高速に実行可能解（近似解）を求めることができます．
整数変数のみを含み，かつすべての変数に上限と下限がある問題に対してのみ有効です．目的関数，制約式に重みを設定することができます．制約の重みには，ハード制約，セミハード制約，ソフト制約の三種類があります． - wls：重み付き局所探索法(WLS)
PySIMPLEから呼び出して使える近似解法です．0-1係数のみを含む制約式に対して特別な処理をおこなっています．そのため，集合被覆や集合分割といった特定の問題を得意としています．線形及び二次の制約式・目的関数を扱うことができます．問題が二次式を含む場合は整数変数のみを扱うことができ，すべて線形式の場合は連続変数も扱うことができます． - rcpsp：資源制約付きスケジューリング問題ソルバ（RCPSP）
京都大学「問題解決エンジン」グループの開発による資源制約付きスケジューリング問題に対するアルゴリズムです．資源制約の下，決められた作業の開始・終了時刻を決定する問題の実行可能解を高速に求めることができます．rcpspの記述にあたっては問題をC++SIMPLEの特殊なクラスを用いて記述する必要があります．完了時刻の最小化問題と，納期遅れ最小化問題を扱うことができます．前者を扱う際にはソフト制約，後者を扱う際にはハード制約のみが使用できます．
Nuorium Optimizerのアルゴリズムは，SIMPLEで記述される目的関数，制約で四則演算および数学関数を用いて記述されたものをサポートします．
上に戻る