1.3 数理最適化問題一覧
扱う問題の構成は以下の通りです．表における○は，それぞれの問題が，どのような種類の数理最適化問題に属するかを表しています．例えば，ナップサック問題は混合線形整数計画問題です．
LPは線形計画問題，MIP（MILP）は混合線形整数計画問題，QPは二次計画問題，NLPは非線形計画問題，SDPは半正定値計画問題，WCSPは重み付き制約充足問題，RCPSPは資源制約付きスケジューリング問題を意味します．
| 問題 | LP | MIP | QP | NLP | SDP | WCSP | RCPSP |
|---|---|---|---|---|---|---|---|
| 配合問題 | ○ | ||||||
| 輸送問題 | ○ | ||||||
| 多期間計画問題 | ○ | ||||||
| 包絡分析法（DEA）モデル | ○ | ||||||
| ナップサック問題 | ○ | ||||||
| 集合被覆問題 | ○ | ||||||
| 最大流問題 | ○ | ||||||
| 最小費用流問題 | ○ | ||||||
| 多品種流問題 | ○ | ||||||
| pメディアン問題 | ○ | ||||||
| pセンター問題 | ○ | ||||||
| 巡回セールスマン問題 | ○ | ||||||
| 割当問題 | ○ | ○ | |||||
| 二次割当問題 | ○ | ||||||
| 設備計画問題 | ○ | ||||||
| 最小二乗問題 | ○ | ||||||
| ポートフォリオ最適化問題 | ○ | ||||||
| ロジスティック回帰モデル | ○ | ||||||
| イールドカーブ推定問題 | ○ | ||||||
| 格付け推移行列推定問題 | ○ | ||||||
| 相関行列取得問題 | ○ | ||||||
| ロバストポートフォリオ最適化問題 | ○ | ||||||
| 最大カット問題 | ○ | ○ | ○ | ||||
| セミナー割当問題 | ○ | ||||||
| ジョブショップスケジューリング問題 | ○ |
最後に，ご利用になられる環境（コンパイラ等）の違いにより，お手元で実行した際以下のような解が得られる可能性がございますのでご注意ください．
- 本例題集に記載した解と微小に異なる解
- （最適解が複数ある問題や，WCSP/RCPSPを適用した場合に関して）本例題集に記載した解と異なる解
上に戻る