組合せ最適化
組合せ最適化（Combinatorial optimization。組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学と情報工学での最適化の一部であり、オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、一般に難しいと思われる問題を解くために、その問題の広大な解空間を探索する。組合せ最適化のアルゴリズムは、解空間を狭めたり、効率的に探索を行う。
組合せ最適化アルゴリズムは命令型プログラミング言語やPrologのような宣言型プログラミング言語で実装されることが多い。あるいは少し妥協してHaskellのような関数型言語やLISPのようなマルチパラダイム言語が使われることもある。
計算複雑性理論の研究は、組合せ最適化に役立っている。組合せ最適化アルゴリズムは、一般にNP困難である問題に関係している。そのような問題は、一般に効率的に解けるとは思われない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか（例えば「小さな」問題）が効率的に解けることを示唆する。組合せ最適化は実にそのケースであり、そのような例はしばしば重要な応用が可能である。
非形式的定義
組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最もよい解決法を見つけることである。
形式的定義
組合せ最適化問題のインスタンスは、の要素の組 (tuple) として形式的に記述できる。
ここで
- X は解空間（solution space、その中に f と P が定義されている）
- P は実現可能かどうかを判定する関数
- Y は実現可能な解の集合
- f は最適化関数
- extr は極値（extreme、最大または最小）
問題例
手法
以下の発見的探索法（メタヒューリスティックアルゴリズム）は、この種の問題を解くのに使われる。
関連項目
これらの手法に関しては効率が最も重視される。すなわち、全てのタイプの問題についてどの探索手法が最も効率的か、である。その質問への答えは90年代にノーフリーランチ定理で示された。