組合せ最適化

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

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

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

形式的定義
組合せ最適化問題のインスタンスは、  の要素の組 (tuple) として形式的に記述できる。

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

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

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

手法

 一般的な手法 

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

 特定の問題に対する手法 
 最短経路問題
 ダイクストラ法
 ベルマン-フォード法
 最小全域木
 プリム法
 クラスカル法
 ブルーフカ法
 最大フロー問題・最小カット問題
 フォード・ファルカーソンのアルゴリズム
 エドモンズ・カープのアルゴリズム
 ディニッツ法
 プリフロープッシュ法
 巡回セールスマン問題
 最近傍法
クリストフィードのアルゴリズム

 ヒューリスティックを使用する物 
 局所探索法、山登り法
 最良優先探索
 A*

 メタヒューリスティック 

以下の発見的探索法（メタヒューリスティックアルゴリズム）は、この種の問題を解くのに使われる。
 近傍探索法 
 局所探索法
 焼きなまし法
 タブーサーチ

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

 その他のアルゴリズム 
 GRASP
 Population-based incremental learning
 シミュレーティド・エボリューション
 Reactive search

 参考文献 
 B.コルテ、J.フィーゲン：「組合せ最適化 [原書6版]：理論とアルゴリズム」、丸善、ISBN 978-4-621-30762-5 (2022年11月).
 河原吉伸、永野清仁：「劣モジュラ最適化と機械学習」、講談社サイエンティフィク、ISBN 978-4-06-152909-0 (2015年12月8日).

関連項目
 探索
 マトロイド
 離散凸解析
 組合せ数学

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

*
Category:組合せ論
Category:最適化
Category:計算複雑性理論
Category:数学に関する記事