本课程共分11章，一共54个视频，总时长810分钟。
在第一章组合最优化引论中，我们将通过节食问题(Diet Problem)引入线性规划模型，并借由一个实例说明一个最小支撑树的整数线性规划模型可以转化为一个线性规划问题进行求解，从而揭示了组合最优化课程的主旨：重点探讨的是这样一类组合最优化问题的模型，其可以描述为整数线性规划问题，但是其松弛的线性规划问题的最优解就是整数规划问题的最优解。接着借助邻域的概念来分析局部最优解和全局最优解之间的关系。为了求解优化问题，需要分析可行区域和目标函数的性质，为此引入凸集和凸函数的定义，由此得到一类重要的凸规划问题，它的特点就是局部最优解等于全局最优解。
第二章学习线性规划的基本理论和单纯形法，首先介绍线性规划的基本可行解的概念，分析其几何性质以及与极点的一一对应性，重点研究线性规划基本定理：只要线性规划问题的可行域非空，则一定存在基本可行解；若线性规划问题存在有限最优解，则最优解必在某极点（基本可行解）上达到。接着学习单纯形法的基本思想、迭代原理和实施步骤，最后学习两个反循环的法则
——Bland规则和字典序法则。
第三章学习线性规划的对偶理论，第一节介绍线性规划的对偶规划。对一般型的线性规划问题，通过单纯形法的最优性准则，分析如何通过两步走法则来写对偶规划：先用对偶关系搭框架，再由五字口诀定符号。第二节介绍线性规划的对偶理论：对称性、弱对偶性、强对偶性和互补松紧性定理。最后引出Kuhn-Tucker最优性条件。第三节介绍最短路问题的线性规划模型及其对偶规划。
第四章学习单纯形法在计算上的优化。首先介绍求解线性规划问题的两阶段法，第一阶段的目的是生成一个基本可行解，用于第二阶段的迭代计算。接着学习修正单纯形法，其目的是减少单纯形法的计算量和存储量，特别适用于系数矩阵A的列数远远大于行数的情况、甚至无法描述A的所有列的情况，对于后者，将修正单纯形法应用到最大流问题上是一个很好的例证。最后学习Dantzig-Wolfe 分解算法。
第五章学习线性规划的原始-对偶算法。首先，分析原始对偶算法的主要思想，每次迭代给定一个对偶可行解，构造其对应的允许列的集合，构造限制原问题RP及其对偶问题DRP，当RP的最优值xopt>0时，求得DRP的最优解，并求出一个参数q，来更新一个目标值更好的对偶可行解，当DRP的最优值等于0时算法迭代中止。进一步分析原始对偶算法的迭代本质，在相邻的两次原始对偶算法的迭代中，允许列的集合J和J*发生了哪些变化呢？最优基中的列一旦进入允许列，就不会再出来，直到迭代终止时，所有最优基的基列都变成允许列，这就保证了原始对偶算法仅在允许列中寻找最优解的正确性。
第六章学习最大流问题。第一节将原始对偶算法应用到最大流问题上。最大流问题的线性规划模型中右端向量b比价值向量c更复杂，所以将其看成对偶问题，组合化右端向量。将DRP问题的求解转化为剩余网络上找从s到t的前向增广路的问题，而每次迭代的最小比值q就是可增广的流量。第二节分析最大流与最小割的关系。最大流的流值等于最小割的容量，标号算法终止时，标号点和未标号点构成了一个最小割，其前向弧必饱和，后向弧必为0弧。第三节介绍最大流问题的预流推进算法。针对增广路算法每次迭代只找一条增广路的缺陷，我们关注每一条弧的操作和处理,每个阶段尽可能多地沿多条路推进流量，这就需要构造特殊的分层网络，各个阶段之间最短路的长度严格递增，直到当前增广网络中不存在增广路，则找到了最大流。最后分析预流推进算法的正确性和时间复杂性为O(|V|3).
第七章学习最小费用流问题。在最小费用流的线性规划模型中，价值向量和右端向量都是一般向量，首先将其看成对偶问题，并将DRP问题的求解转化为求一个负费用的有向圈，得到消圈算法。最小费用路算法将最小费用流问题看成原问题，从零流开始，每次迭代沿一条最小费用路增广流量，直到流量达到v0。第三节介绍运输问题的Alphabeta算法。将运输问题看成原问题，组合化费用向量，每次迭代将RP的求解转化为一个最大流问题，根据发点集和收点集中标号点的集合确定DRP的最优解，计算最小比值，从而更新对偶可行解。最后我们指出运输问题和最小费用流问题是可以相互转化的。
第八章学习匹配问题。一个图是二部图当且仅当它不含有奇圈。一个匹配M是最大匹配，当且仅当图中不含有关于M的交错增广路。第二节学习二部图的匹配算法，从空集匹配开始，构造当前匹配对应的辅助图，寻求一条交错增广路，其对应辅助图中从一个未盖点到一个目标点的路，并沿增广路增广匹配，当找不到增广路时达到最大匹配。进一步，将二部图的匹配算法推广到非二部图时，由于花的结构使得辅助网络上的一条从未盖点到目标点的路，未必对应原网络的一条交错增广路。算法需要识别花的结构，并在收缩花之后将其转化为二部图上的匹配问题。最后分析了时间复杂性和最新研究进展。
第九章学习赋权匹配问题。二部图的赋权匹配问题 也称为指派问题，是运输问题的特殊情况，将Alphabeta算法推广到指派问题，就得到了匈牙利算法。进一步，引入奇集的概念和奇集中匹配边数不超过其基数的一半的约束,得到非二部图上赋权匹配问题的线性规划模型。用原始对偶算法求解该模型时，将RP转化为收缩了极大奇集的允许图上的最大基数匹配问题，这很好地体现了将一般赋权匹配问题转化为一系列基数匹配问题求解的研究思想。最后分析其时间复杂性为O(n4)。
第十章学习最小支撑树与拟阵。首先介绍最小支撑树问题的最优性条件、和求解算法，然后学习瓶颈支撑树问题及其算法，接着学习拟阵的定义、几个重要的概念——基、秩和圈，最后分析两个拟阵的交。
第十一章学习整数线性规划问题。首先介绍优化模型的分类，和优化模型的转化，学习如今将极大极小型、带分式和绝对值的函数及双线性函数转化为线性函数，学习如何通过引入逻辑变量来描述一些逻辑关系的约束条件。当整数线性规划的系数矩阵是全单位模矩阵时，其松弛线性规划问题的最优解必是整数解，因此可以通过求解松弛问题设计多项式时间算法，这也是前面几章以流为框架的组合优化问题的特点。接着介绍求解一般整数线性规划问题的分枝定界法。最后介绍整数线性规划的割平面法，其核心思想就是通过求解一系列松弛的增加了割平面后的线性规划问题，逐步逼近整数规划问题的最优解。
