組合せ最適化

組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。

非形式的定義

組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最も良い解決法を見つけることである。

解が二値ベクトルの場合は0-1最適化問題（英: 0-1 optimization problem）とも言われる。

形式的定義

組合せ最適化問題のインスタンスは、 ${\displaystyle (X,P,Y,f,\mathrm {extr} )}$ の要素の組 (tuple) として形式的に記述できる。

ここで

• X は解空間（solution space、その中に f と P が定義されている）
• P は実現可能かどうかを判定する関数
• Y は実現可能な解の集合
• f は最適化関数
• extr は極値（extreme、最大または最小）

問題例

• 巡回セールスマン問題
• 中国人郵便配達問題
• 最小全域木問題
• 最短経路問題
• 線形計画問題（基底にするべき変数を選ぶ問題と見なすと組合せ的になる）
• 整数計画問題
• エイト・クイーン（制約充足問題の一種）
• ナップサック問題
• 最大フロー問題
• 最小カット問題
• 最大マッチング問題
• 劣モジュラ関数最小化
• 劣モジュラ関数最大化

NP困難

計算複雑性理論の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、NP困難である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか（例えば「小さな」問題）が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。

手法

一般的な手法

• 分枝限定法
• 動的計画法
• 力まかせ探索
• 深さ優先探索
  • 反復深化深さ優先探索
  • 深さ制限探索
• 幅優先探索
• 均一コスト探索
• 双方向探索
• 貪欲法

特定の問題に対する手法

• 最短経路問題
  • ダイクストラ法
  • ベルマン-フォード法
• 最小全域木
  • プリム法
  • クラスカル法
• 最大フロー問題・最小カット問題
  • フォード・ファルカーソンのアルゴリズム
  • エドモンズ・カープのアルゴリズム
• 巡回セールスマン問題
  • 最近傍法
  • クリストフィードのアルゴリズム

ヒューリスティックを使用する物

• 局所探索法、山登り法
• 最良優先探索
• A*

メタヒューリスティック

以下の発見的探索法（メタヒューリスティックアルゴリズム）は、この種の問題を解くのに使われる。

近傍探索法

• 局所探索法
• 焼きなまし法
• タブーサーチ

進化的計算

• 群知能
  • 蟻コロニー最適化
• 進化的アルゴリズム
  • 遺伝的アルゴリズム

その他のアルゴリズム

• GRASP
• Population-based incremental learning
• シミュレーティド・エボリューション
• Reactive search

関連項目

• 探索
• マトロイド
• 離散凸解析

外部リンク

• 組合せ最適化（研究者向けの解説）
• 組合せ最適化応用例
• 簡単そうで難しい組合せ最適化(PDF)
• Andrew Lucas:"Ising formulations of many NP problems", Front.Phys (Feb. 2014)

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）