组合优化是最优化问题的分支学科，研究离散变量组合问题最优解求解方法的数学分支，其目标是从可行解集中寻找使目标函数值最小的解。与连续变量优化存在显著差异，后者涉及求一组实数或函数，而组合优化需从离散集合（有限或可数无限集）中寻找整数、排列、图等特定对象的最优解，典型问题包括旅行商问题、0-1背包问题和装箱问题组合爆炸。

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

典型的组合优化问题有：

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

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

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

装箱问题（Bin Packing Problem）；

图着色问题（Graph Coloring Problem）；

聚类问题（Clustering Problem）；

最大团问题 等。

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