组合优化

组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。来源：《组合最优化算法和复杂性》，高等教育出版社，1988，C.H. Papadimitriou, K. Steiglitz （刘振宏，蔡茂诚 译）

概念定义

组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω={s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)=minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。

问题分类

典型的组合优化问题有：

旅行商问题（Traveling Salesman Problem－TSP）；

加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）；

0-1背包问题（Knapsack Problem）；

装箱问题（Bin Packing Problem）；

图着色问题（Graph Coloring Problem）；

聚类问题（Clustering Problem）；

最大团问题 等。

这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。