本模块将介绍整数线性规划及其在解决 NP 难（组合优化）问题中的应用。我们将举例说明什么是整数线性规划，如 Knapsack、Vertex Cover 和 Graph Coloring 等问题。接下来，我们将学习积分差距的概念，并研究顶点覆盖问题的积分差距特例。最后，我们将讲解如何使用 python 库 Pulp 编制和求解整数线性规划。

我们将介绍解决 NP 难问题的近似算法。这些算法速度很快（通常是贪婪算法），可能不会产生最优解，但能保证其解与最佳解不会 "相差太远"。我们将从对相关概念的基本介绍开始，介绍其中的一些算法，然后介绍调度问题、顶点覆盖问题和最大可满足性问题的一系列近似算法。

我们将介绍旅行推销员问题（TSP）：一个非常重要且广泛应用的组合优化问题、其 NP 难度以及用常数因子逼近一般 TSP 的难度。 我们将介绍整数线性规划公式和一种简单而优雅的动态规划算法。我们将介绍 Christofides 提出的 3/2 因子近似算法，并讨论一些求解 TSP 的启发式方法。最后，我们将介绍 knapsack 问题的近似方案。