Integer programming — 整数规划

整数规划（IP；英语：integer programming）是数学优化的一个分支，主要研究在部分或全部变量被约束为只能取整数值的优化问题。

研究最深入的特例是整数线性规划（ILP；英语：integer linear programming），其目标函数和约束条件均为线性。与线性规划（其中变量可以取任意实数值）不同，整数约束使得整数规划问题在求解上要困难得多。

整数规划在经济学、物流、生产计划以及其他变量本质上是离散的领域（例如，生产产品的单位数量或员工人数）中有着广泛的应用。

定义与术语

一般的整数线性规划问题可以表述如下：

寻找一个向量 $x$，使其：

最大化（或最小化） $c^{T}x$

满足以下约束条件：

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$（向量 $x$ 的所有分量均为整数）

其中 $x$ 是变量向量，$c$ 和 $b$ 是向量，$A$ 是系数矩阵。

根据对变量的要求，可将问题分为以下几类：

• 纯整数规划：所有变量都必须是整数。
• 混合整数规划（英语：mixed-integer programming, MIP）：只有部分变量必须是整数。
• 0-1整数规划（或称布尔规划）：变量只能取 0 或 1，这可以用于建模「是/否」类型的逻辑决策。

关键特性与复杂性

计算复杂性

一般而言，整数线性规划问题是 NP-hard 的。这意味着目前不存在已知的能在多项式时间内为任意整数规划问题找到精确最优解的算法。其复杂性源于问题的组合性质，因为可能的整数解的数量会随着变量数量的增加而呈指数级增长。

与线性规划的联系（LP 松弛）

对于任何整数规划问题，都可以构建其线性松弛（LP relaxation）问题——即移除变量的整数约束而得到的线性规划（LP）问题。LP 松弛的解具有两个重要特性：

1. 它的求解速度要快得多（可在多项式时间内完成）。
2. LP 松弛的最优目标函数值为原始整数问题的最优值提供了一个界限（对于最大化问题是上界，对于最小化问题是下界）。

然而，简单地将 LP 松弛的非整数解四舍五入到最接近的整数，通常不会得到整数规划问题的最优解，甚至可能不是可行解。

全幺模性属性

存在一类重要的整数线性规划问题，其求解难度与其 LP 松弛相当。这类问题的约束矩阵 $A$ 是完全幺模的（即其任何方子矩阵的行列式都等于 0、+1 或 -1）。如果矩阵 $A$ 是完全幺模的，并且向量 $b$ 是整数向量，那么 LP 松弛可行域的所有顶点都将自动是整数。因此，通过单纯形法找到的解必定是整数解。这类问题的例子包括运输问题和指派问题。

求解方法

对于不具备完全幺模性的一般整数规划问题，已开发出基于隐式枚举思想的精确求解方法。

• 分支定界法（英语：Branch and Bound）—— 一种主要的精确求解方法，它通过系统地将可行解集划分为子集（分支），并剪除那些显然不包含最优解的子集（定界）。LP 松弛被用于评估子集是否具有继续搜索的潜力。

• 割平面法（戈莫理割平面法；英语：Cutting Plane Method）—— 一种迭代方法，它向问题中逐步添加新的线性约束（即「割平面」）。这些割平面会「切掉」LP 松弛的非整数解，同时不排除任何可行的整数解，从而逐步使 LP 松弛的可行域逼近整数解的凸包。

现代求解器通常采用混合算法，例如分支切割法（英语：Branch and Cut），该方法结合了以上两种方法的优点。

示例与应用领域

整数规划可以为许多经典的组合优化问题建模。

• 背包问题：一个经典的 0-1 规划问题，目标是在不超过总重量限制的情况下，选择一组物品，使其总价值最大。
• 旅行商问题：寻找一条经过一系列给定城市的最短路径。该问题可以被建模为一个整数规划问题，其中变量表示是否将图中的某条边包含在最终路径中。

由于其灵活性，整数规划是运筹学中应用最广泛的工具之一，应用于以下领域：

• 物流与供应链管理：运输路线优化、仓库选址、库存管理。
• 生产计划：制定生产调度、资源分配、设备负载安排。
• 金融与经济：投资组合构建、资本预算。
• 电信与能源：通信网络设计、发电机组调度。