数理計画問題とアルゴリズム一覧
数理計画問題
LP (Linear Programming : 線形計画問題)
目的関数と制約式がすべて線形である問題で、整数変数を含まないもの
MILP (Mixed Integer Linear Programming : 混合整数計画問題)
目的関数と制約式がすべて線形で、整数変数を含むもの
MIP(Mixed Integer Programming)と呼ばれることも多い
MIQP (Mixed Integer Quadratic Programming : 混合整数二次計画問題)
制約式がすべて線形、目的関数が二次関数で、整数変数を含むもの
MINLP (Mixed Integer Nonlinear Programming : 混合整数非線形計画問題)
制約式および目的関数が非線形で整数変数を含むもの
CQP (Convex Quadratic Programming : 凸二次計画問題)
目的関数が凸な二次関数、制約式がすべて線形であるもの
(ただし、目的関数の符号の変更で下に凸な目的関数の最小化に帰着できるもの)
CP (Convex Programming : 凸計画問題)
目的関数、制約式に非線形なものが含まれているが、実行可能領域が凸で、目的関数の符号の変更で下に凸な目的関数の最小化に帰着できる問題ここでは整数変数は含まないものを指す
半正定値計画問題も凸計画問題の一部ですが、ここには含めない
NLP (Nonlinear Programming : 非線形計画問題)
上記以外で、整数変数を含まない一般の非線形計画問題
SDP (SemiDefinite Programing : 半正定値計画問題)
行列の半正定値制約を含む線形計画問題
NLSDP (NonLinear SemiDefinite Programing : 非線形半正定値計画問題)
行列の半正定値制約を含み、なおかつ目的関数・制約式に非線形項が含まれる問題
WCSP (Weighted Constraint Satisfaction Problem : 重み付き制約充足問題)
各々重みの付いた制約条件をなるべく満足するためには値をどのように割り当てると良いかを決定する問題
制約充足問題ソルバwcspにより高速に解を得ることができる
RCPSP (Resource Constrained Project Scheduling Problem : 資源制約付きスケジューリング問題)
一定の資源制約の下で、決められた作業の開始・終了時刻を決定する問題 一般の整数計画問題(MILP)として記述することも可能だが、特殊な記法を行うと資源制約付きスケジューリング問題ソルバrcpspにより高速に実行可能解を得ることができる
アルゴリズム一覧
simplex : 単体法()
線形計画法の解法として古くから知られている方法です．大規模問題では内点法に速度的に劣りますが，可能基底解が求まり原理的に内点法/外点法よりも高精度です．
整数変数を含む問題に対して指定すると，単体法を分枝限定法(Branch and bound method)という枠組のなかで繰り返し行って，最適性の保証のある整数解を求めます．大規模問題において基底解が必要な場合には，"cross:on"と指定して内点法からのクロスオーバーを用いるのが有利です．
dual_simplex : 双対単体法(DUAL_SIMPLEX)
(主)単体法が主実行可能な基底解をたどりながら最適解にたどり着くのに対し，双対単体法は双対実行可能な基底解をたどりながら最適解にたどり着きます．
大規模な線形計画問題に対して，(主)単体法と比較して有利であることがあります．
asqp : 有効制約法(ACTIVE_SET_QP)
単体法と同様，古典的な凸二次計画問題の厳密解法です．1万変数以上の大規模問題では，一般に内点法(直線探索法(Line Search Method))に劣りますが，
変数に比べて制約式の数が非常に少ない(1/10以下)場合
目的関数のヘッセ行列が密行列である場合
には内点法よりも高速かつ高精度です．また，整数計画法に対応しているので，整数変数が含まれている凸二次計画問題を解くことができます．"cross:on"と指定することで内点法からのクロスオーバーを用いることができるので，大規模問題に対して高精度な解を求めることができます．
higher : 線形計画問題専用内点法(HIGHER_ORDER)
線形計画法に特化した内点法で，大規模な線形計画問題の解法としては最も高速です．単体法と違い，可能基底解は求まりません．
lipm : (新版)直線探索法(LINE_SEARCH_IPM)
lepm : 直線探索外点法(LINE_SEARCH_EPM)
line : (旧版)直線探索内点法(LINE_SEARCH)
一般の凸計画問題に適用可能な内点法・外点法です．問題が凸であることがわかっている場合には信頼領域法よりも高速です．幅広い範囲の問題に対して有効なのが内点法(lipm)，外点法(lepm)は問題に対して比較的良い初期値が得られている場合に有効であることが示されています．旧版の内点法(line)は，以前のバージョンとの整合を取る場合にご利用ください(Ver.7以前の内点法lineとVer.8以降の内点法lipmでは，メリット関数の定義が若干異なっておりますので，新版と旧版では異なる結果を与える場合があります)．
bfgs : 準ニュートン法(BFGS_LINE_SEARCH)
準ニュートン法によって二階微係数を求める内点法です．“bfgs”はヘッセ行列の近似行列を密行列として保持しますので，小規模(50～500変数以下)な非線形計画問題に適しています．
tipm : (新版)信頼領域内点法(TRUST_REGION_IPM)
tepm : 信頼領域外点法(TRUST_REGION_EPM)
trust : (旧版)信頼領域法内点法(TRUST_REGION)
大規模なものを含む一般の非線形計画問題に適用可能な内点法・外点法です．幅広い範囲の問題に対して有効なのが内点法(tipm)，外点法(tepm)は問題に対して比較的良い初期値が得られている場合に有効であることが示されています．旧版の内点法(trust)は，以前のバージョンとの整合を取る場合にご利用ください(Ver.7以前の内点法trustとVer.8以降の内点法tipmでは，メリット関数の定義が若干異なっておりますので，新版と旧版では異なる結果を与える場合がございます)．
lsqp : 直線探索法に基づく逐次二次計画法(LINE_SEARCH_SQP)
準ニュートン法によって二階微係数を求める逐次二次計画法です．小規模(50～100変数以下)な非線形計画問題に適しています．
問題によっては直線探索内点法/外点法(lipm/lepm/line)よりも安定的により精度の良い解を導くことができます．
tsqp : 信頼領域法に基づく逐次二次計画法(TRUST_REGION_SQP)
二階微係数をそのまま用いる逐次二次計画法です．大規模なものを含む一般の非線形計画問題に適用可能な方法です．一般に内点法よりも低速ですが，問題によっては内点法よりも安定的に，より精度の良い解を導くことができます．
変数の数よりも制約式数が多い場合には内点法/外点法(tipm/tepm/trust)よりも高速な場合があります．
slpsqp : 逐次線形二次計画法(SLP-SQP)
ペナルティ関数を用いない逐次線形二次計画法です．ある程度大規模なものを含む一般の非線形計画問題に適用可能です．大域的収束性を保証する原理が内点法/外点法(tipm/tepm/trust)や従来の逐次二次計画法(lsqp/tsqp)のものとは異なるため，他の方法で収束しない問題に対して有効な場合があります．また，制約式の勾配が小さい反復点にいる時，実行可能領域に接近するという仕組みが組み込まれていますので複雑な制約においても安定的な動作が期待できます．
lsdp : 線形半正定値計画問題に対する主双対内点法
線形の半正定値計画問題に対する主双対内点法です．目的関数・制約式に出現する項は線形である必要があります．内部でメリット関数の計算を行いません．
csdp : 凸半正定値計画問題に対する主双対内点法
目的関数が凸非線形関数で，制約が線形な半正定値計画問題に対する主双対内点法です．この類の問題は，線形半正定値計画問題で記述することができますが，そのまま扱った方が高速に求解できます．内部でメリット関数の計算を行う点がlsdpと異なります．
qnsdp : 準ニュートン法を用いた非線形半正定値計画問題に対する主双対内点法
目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です．メリット関数の降下を保証するために，準ニュートン法を利用しています．
lmsdp : Levenberg-Marquardt法を用いた非線形半正定値計画問題に対する主双対内点法
目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です．メリット関数の降下を保証する為に，Levenberg-Marquardt法を利用しています．準ニュートン法に基づく方法(qnsdp)に比べて，規模の大きな問題を取り扱う事ができます．変数が少なく，行列次元が大きい問題の場合，信頼領域法に基づく方法(trsdp)より高速な場合があります．
trsdp : 信頼領域法を用いた非線形半正定値計画問題に対する主双対内点法
目的関数・制約式に非線形項が出現する半正定値計画問題に対する主双対内点法です．メリット関数の降下を保証するために，信頼領域法を利用しています．準ニュートン法に基づく方法(qnsdp)より規模の大きな問題を取り扱う事ができます．
wcsp : 制約充足問題ソルバ(WCSP)
京都大学「問題解決エンジン」グループの開発による制約充足問題に対するアルゴリズムです．必ずしも厳密解が求まるわけではありませんが，大規模な整数計画問題に対し，非常に高速に実行可能解(近似解)を求めることができます．
整数変数のみを含み，かつすべての変数に上限と下限がある問題に対してのみ有効です．目的関数，制約式に重みを設定することができます．制約の重みには，ハード制約，セミハード制約，ソフト制約の三種類があります．
wcsplp : 混合整数計画問題専用の制約充足問題ソルバ
線形な混合整数計画問題を制約充足問題の枠組みで解くアルゴリズムです．このアルゴリズムでは，連続変数は適当な刻み幅をもつDiscreteVariableと解釈されます．wcsplpでは全ての制約式をハード制約として扱い，目的関数をソフト制約として扱います．
rcpsp : 資源制約付きスケジューリング問題ソルバ(RCPSP)
京都大学「問題解決エンジン」グループの開発による資源制約付きスケジューリング問題に対するアルゴリズムです．資源制約の下，決められた作業の開始・終了時刻を決定する問題の実行可能解を高速に求めることができます．rcpspの記述にあたっては問題をSIMPLEの特殊なクラスを用いて記述する必要があります．完了時刻の最小化問題と，納期遅れ最小化問題を扱うことができます．前者を扱う際にはソフト制約，後者を扱う際にはハード制約のみが使用できます．
数理計画問題とアルゴリズムの対応
| LP | MILP | MIQP | MINLP | CQP | CP | NLP | SDP | NLSDP | RCPSP | |
|---|---|---|---|---|---|---|---|---|---|---|
| simplex | ○ | ○ | -- | -- | -- | -- | -- | -- | -- | △ |
| dual_simplex | ○ | -- | -- | -- | -- | -- | -- | -- | -- | -- |
| asqp | ○ | -- | ○ | -- | ○ | -- | -- | -- | -- | -- |
| higher | ○ | -- | -- | -- | -- | -- | -- | -- | -- | -- |
| lipm/lepm/line | △ | -- | -- | -- | ○ | ○ | -- | -- | -- | -- |
| bfgs | △ | -- | -- | -- | -- | △ | ○ | -- | -- | -- |
| tipm/tepm/trust | △ | -- | -- | -- | -- | △ | ○ | -- | -- | -- |
| lsqp | △ | -- | -- | -- | △ | ○ | ○ | -- | -- | -- |
| tsqp | △ | -- | -- | -- | △ | ○ | ○ | -- | -- | -- |
| slpsqp | △ | -- | -- | -- | △ | ○ | ○ | -- | -- | -- |
| lsdp | △ | -- | -- | -- | △ | △ | -- | ○ | -- | -- |
| csdp | △ | -- | -- | -- | △ | △ | -- | ○ | -- | -- |
| qnsdp | △ | -- | -- | -- | △ | △ | △ | △ | ○ | -- |
| trsdp | △ | -- | -- | -- | △ | △ | △ | △ | ○ | -- |
| lmsdp | △ | -- | -- | -- | △ | △ | △ | △ | ○ | -- |
| wcsp | -- | ○※1 | ○※1 | ○※1 | -- | -- | -- | -- | -- | -- |
| wcsplp | △ | ○※2 | -- | -- | -- | -- | -- | -- | -- | -- |
| global | △ | △ | △ | ○ | △ | △ | ○ | ○ | ○ | △ |
| DFO | △ | -- | -- | -- | △ | △ | ○ | -- | -- | -- |
| rcpsp | -- | -- | -- | -- | -- | -- | -- | -- | -- | ○ |
Info
※1: 0-1整数変数と離散変数のみを含む問題に対して適用できることを意味する
連続変数を含む問題あるいは上限と下限を持たない整数変数を含む問題には適用できない
※2: 連続変数を含む場合も適用ができるが効率が落ちる可能性がある