KNOWECON WIKI

ARTICLE

整数规划

整数规划 (Integer Programming) 整数规划（Integer Programming，简称IP）是数学规划 (Mathematical Programming) 和运筹学 (Operations Research) 的一个重要分支，是线性规划 (Linear Programming) 的自然延伸。它研究的是在一组线性约束条件下优化一个线性目

浏览 3 更新 2026-05-25

整数规划 (Integer Programming)

整数规划（Integer Programming，简称IP）是数学规划 (Mathematical Programming) 和运筹学 (Operations Research) 的一个重要分支，是线性规划 (Linear Programming) 的自然延伸。它研究的是在一组线性约束条件下优化一个线性目标函数的问题，但附加了一个关键限制：部分或全部决策变量 (Decision Variables) 必须取整数值。

现实世界中许多决策变量天然具有不可分割的性质，如生产机器的台数、分配的员工人数、项目投资的个数等。整数规划正是为处理这类离散决策问题而发展起来的数学工具。然而，这一看似微小的整性约束使得整数规划的求解难度远大于线性规划——几乎所有非平凡的整数规划问题都是NP-难 (NP-hard) 的。

整数规划的分类

根据决策变量中整数变量的范围和类型，整数规划可分为以下几个主要类别：

  1. 纯整数规划 (Pure Integer Programming)：所有决策变量都必须取整数值。例如，x1,x2,…,xn∈Z≥0 x_1, x_2, \ldots, x_n \in \mathbb{Z}_{\ge 0} 。
  1. 混合整数规划 (Mixed Integer Programming, MIP)：只有一部分决策变量受整性约束，其余变量可以取连续实数值。这是实际应用中最常见的形式。
  1. 0-1整数规划 (Binary Integer Programming)：决策变量只能取值0或1，也称为二值规划。这类规划非常适合于建模"是/否"类型的逻辑决策，如是否投资某个项目、是否选择某条路径、是否在某地选址等。

与线性规划的关键区别：可行域

整数规划与线性规划最本质的区别在于可行域的结构。

  • 线性规划的可行域是一个凸集 (Convex Set)——具体表现为一个凸多面体，其最优解必然在可行域的某个顶点取得，这使得单纯形法 (Simplex Method) 能够高效地在顶点之间搜索。
  • 整数规划的可行域由可行多面体内所有整数格点组成，这是一个离散的点集，失去了凸性。最优解通常不在连续松弛的顶点处，而可能位于内部。

可行域的这种离散性意味着许多在线性规划中行之有效的优良性质（如最优解的全局可达性、灵敏度分析的简便性）在整数规划中不再成立。

线性规划松弛 (LP Relaxation)

求解整数规划的起点往往是它的线性规划松弛 (LP Relaxation)：即暂时去掉所有整性约束，将问题转化为一个标准的线性规划来求解。

设整数规划（最大化）为：

zIP∗=max⁡{cTx∣Ax≤b, x∈Z+n}z_{IP}^* = \max \{ c^T x \mid Ax \le b, \, x \in \mathbb{Z}_+^n \}

其LP松弛为：

zLP∗=max⁡{cTx∣Ax≤b, x≥0}z_{LP}^* = \max \{ c^T x \mid Ax \le b, \, x \ge 0 \}

关键不等式：zIP∗≤zLP∗ z_{IP}^* \le z_{LP}^* 。LP松弛的最优值提供了整数规划最优目标值的上界（最大化问题）或下界（最小化问题）。这个界是所有精确求解算法的核心依据。

但需注意，即使LP松弛的最优解碰巧全为整数，它自然是原整数问题的最优解；然而这种情况十分罕见。更常见的是，LP松弛的最优解含有分数分量，不能直接取整——简单的四舍五入往往会违反约束或显著偏离真实最优解。

精确求解方法

一、分支定界法 (Branch and Bound)

分支定界法 (Branch and Bound, B\&B) 是最经典、应用最广泛的整数规划精确求解算法，由A. H. Land和A. G. Doig于1960年提出。其核心思想是"分而治之"。

  • 分支 (Branching)：在当前问题中选取一个取分数值的整数变量 xj x_j ，以其分数值为界将问题拆分为两个（或多个）子问题。例如 xj≤⌊f⌋ x_j \le \lfloor f \rfloor 和 xj≥⌈f⌉ x_j \ge \lceil f \rceil 。
  • 定界 (Bounding)：为每个子问题求解LP松弛，得到该分支的目标值上界。
  • 剪枝 (Pruning)：若一个子问题的上界不优于当前已知的最佳整数可行解（即现任最优），则可安全地剪去该分支，无需再向下探索。

B\&B本质上是一棵搜索树，剪枝操作是算法效率的保证。

二、割平面法 (Cutting Plane Method)

割平面法 (Cutting Plane Method) 由Ralph Gomory于1958年提出。其基本思想是：不断向LP松弛问题中添加额外的线性不等式（称为割），这些割将LP松弛可行域中不包含任何整数解的部分"切除"，同时保留所有整数可行解。随着割的累加，LP松弛的可行域逐渐逼近整数规划的凸包 (Convex Hull)，最终LP松弛的最优解自然成为整数解。

最著名的割是Gomory割 (Gomory Cut)，它直接从单纯形表的分数行推导而来。

三、分支切割法 (Branch and Cut)

现代高性能整数规划求解器（如CPLEX、Gurobi、SCIP）普遍采用分支切割法 (Branch and Cut)——将分支定界与割平面结合起来。在搜索树的每个节点，先尝试生成割平面来收紧LP松弛（若可能），然后再进行分支。这种方法大大压缩了搜索空间，是现代整数规划算法的实际标准。

典型应用

整数规划的应用遍布各个领域：

  • 背包问题 (Knapsack Problem)：在一定容量限制下选择物品以最大化总价值——最经典的0-1整数规划。
  • 旅行商问题 (Travelling Salesman Problem, TSP)：寻找访问所有城市恰好一次并返回起点的最短回路。
  • 设施选址 (Facility Location)：决定在哪些位置建立仓库或工厂，以最小化建设成本与运输成本之和。
  • 生产调度 (Production Scheduling)：在多台机器上安排多个作业的加工顺序以最小化完工时间。
  • 网络设计 (Network Design)：在通信、电力等网络中确定链路容量和路由方案。

计算复杂度

整数规划属于理论计算机科学中的NP-难问题。这意味着不存在已知的多项式时间算法能保证对所有实例求解。尽管如此，现代求解器结合B\&B、割平面、启发式算法和预处理技术，已能够高效求解具有数十万变量和约束的大规模工业问题。成功的关键在于利用问题的特殊结构和有效的模型构建策略。