组合最优化又称组合规划，是在给定有限集的所有具备某些特性的子集中，按某种目标找出一个最优子集的一类数学规划。初期，它所研究的问题，如广播网的设计、旅游路线的安排、课程表的制订等，都是网络上的一些极值问题。后来，对这些问题进行概括和抽象，在理论上研究了拟阵中一些更一般的组合最优化问题及算法。主要研究内容有：线性组合最优化问题；网络上的最优化问题；独立系统和拟阵，拟阵是组合优化中一个基本而重要的概念，许多组合问题都可化为拟阵问题。贪心算法是求拟阵的最优独立集的简单算法；交错链算法是求解最优交问题的基本算法。对问题算法的分类也是一类主要研究内容。某些算法具有多项式时间复杂度，如贪心算法、交错链算法，称之为多项式时间算法，能用多项式算法求解的问题为P问题。还有一类问题从求解的计算量角度看有如下共性：①它们都未找到多项式算法。②若对其中的某一个问题存在多项式算法，则这一类的所有问题也都有多项式算法。这些问题组成的等价类称为NP完备问题，如装箱问题、推销员问题等。人们在求解这类问题时，往往采用“启发式”算法，不能保证求得最优解，但常常能求得较好的近似解。