【地図】数理最適化の全体像と分類

数理最適化を学習していると、「〇〇モデル」「〇〇問題」「〇〇法」といった用語が次々と登場し、混乱することがありました。

例えば「ナップサック問題」と「線形計画問題」。どちらも「問題」とつきますが、前者は課題の構造を指し、後者は数式の形式を指しています。さらに「動的計画法」のようなアルゴリズムも混ざってくるため、「これはモデルなのか？ 課題そのものなのか？ 解き方なのか？」という分類が曖昧になりがちです。

数理最適化の全体像を整理するために、用語を「数理モデル（数式）」「構造（課題パターン）」「解法（アルゴリズム）」の3つのレイヤーに分類しました。

基本数理モデル

数理モデルとは、問題を 変数, 制約, 目的関数に分解し、数式として表現する形式のことである

変数の種類	数式の形	モデル名
実数	線形	線形計画問題（LP）
実数	二次	二次計画問題（QP）
実数	非線形	非線形計画問題（NLP）
整数	線形	整数計画問題（IP）
実数＋整数	線形	混合整数計画問題（MILP）
実数＋整数	二次	混合整数二次計画問題（MIQP）
実数＋整数	非線形	混合整数非線形計画問題（MINLP）

※ 「線形計画問題」などは慣習的な名称であり、ここでは数理モデルの型を指すものとして扱う

数理モデルの性質

同じモデルでも難しさや意味を決める要素が存在する

分類	内容
整数の特殊形	0-1整数
凸性	凸 非凸
不確実性	確率最適化 ロバスト最適化
目的	単目的 多目的
計算困難性	P NP困難 NP完全

構造による問題の分類

構造による問題とは、現実の課題中で、「変数や制約に典型的な構造」が現れるものを、解く対象として抽象化した呼び名である

構造名	代表的な問題	主なモデル	モデルの性質
ネットワーク	最短経路問題	LP
^	最大流問題	LP
マッチング	割当問題	LP	凸
^	ペアリング問題	IP	NP困難
フロー	輸送問題	LP
^	物流問題	LP
ツリー	最小全域木	LP
巡回構造	巡回セールスマン	IP	0-1整数
パッキング	ナップサック問題	IP	0-1整数
^	ビンパッキング問題	IP/MILP	0-1整数 NP困難
カバーリング	集合被覆	IP	0-1整数 NP困難
配置	施設配置問題	IP	0-1整数 NP困難
^	P-メディアン問題	IP	NP困難
ルーティング	車両経路問題	IP/MILP	0-1整数 NP困難
複合構造	スケジューリング	MILP	0-1整数 NP困難

解法の分類

解法とは、数理モデルとして定式化された問題を、実際に計算して解を求めるためのアルゴリズムのことである

厳密な解を得る解法

数理的な根拠に基づき、理論上の正解を導き出す。

対象モデル	解法
LP	単体法
^	内点法
QP/凸NLP	勾配法
^	ニュートン法
^	準ニュートン法
IP/MILP	分枝限定法
^	分枝価格法
^	カット平面法
特定の組合せ問題	動的計画法

※ 対象モデルは代表例であり、実際には前提条件（凸性など）に依存する

近似的な解を得る解法

完璧ではないが、現実的な時間内に「十分に良い答え」を出す。

理論保証あり

解法	典型例
貪欲法	最小全域木
近似アルゴリズム	集合被覆
緩和＋丸め	LP -> IP

理論保証なし

解法	典型例
局所探索法	ナップサック問題
焼きなまし法	巡回セールスマン問題
遺伝的アルゴリズム	ビンパッキング問題

最後に

数理最適化は奥が深く、専門用語の海で迷子になりがちです。
同じように学習中の方にとって、この整理が少しでも「現在地」を知るための羅針盤になれば幸いです。
（もし誤りがある場合はご指摘ください）