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

中文名：组合优化

外文名：Combinatorial Optimization

释义：组合问题的可行解集中求出最优解

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

生产调度问题（Production Scheduling Problem，如Flow-Shop，Job-Shop）；

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

装箱问题（Bin Packing Problem）；

图着色问题（Graph Coloring Problem）；

聚类问题（Clustering Problem）；

最大团问题 等。

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