KNOWECON WIKI

ARTICLE

割平面法

割平面法 (Cutting Plane Method) 割平面法是求解整数规划（Integer Programming, IP）问题的经典算法之一，由拉尔夫·戈莫里（Ralph E. Gomory）于1958年提出，因此也称为戈莫里割平面法。该方法是处理线性整数规划（ILP）中整数约束的核心技术——当求解线性规划松弛得到的最优解不具备整数性时，算法通过系统性

浏览 0 更新 2025-11-08

割平面法 (Cutting Plane Method)

割平面法是求解整数规划（Integer Programming, IP）问题的经典算法之一，由拉尔夫·戈莫里（Ralph E. Gomory）于1958年提出，因此也称为戈莫里割平面法。该方法是处理线性整数规划（ILP）中整数约束的核心技术——当求解线性规划松弛得到的最优解不具备整数性时，算法通过系统性地引入额外的线性不等式（即"割平面"）来剔除当前非整数解，同时保留所有可行整数解，最终在反复迭代中获得整数最优解。

核心思想

割平面法的基本逻辑建立在一个简单的几何直觉之上：整数线性规划的可行域是线性规划松弛可行域中的格点集合。LP 松弛的最优解往往位于松弛可行域的顶点，如果该顶点包含非整数分量，就必须通过新增约束条件将这个顶点"切割"掉，但不得损失任何整数格点。

从代数角度看，每个新添加的约束不等式称为一个"割平面"（cutting plane），它满足两个关键性质：

  • 可行性保留：当前所有整数可行解均满足该不等式。
  • 割除作用：当前的分数 LP 最优解不满足该不等式，因此被排除在缩小后的可行域之外。

满足上述条件的割平面常被称为"合法割"（valid cut）或"戈莫里割"（Gomory cut）。算法不断堆叠割平面，构成一系列逐步缩小的 LP 可行域，直至某个 LP 松弛的极点为整数解。

戈莫里割的代数推导

考虑纯整数规划问题的标准型：

max⁡  c⊤x,s.t. Ax≤b,  x≥0,  xj∈Z≥0\max \; \mathbf{c}^\top \mathbf{x}, \quad \text{s.t. } \mathbf{Ax} \le \mathbf{b}, \; \mathbf{x} \ge \mathbf{0}, \; x_j \in \mathbb{Z}_{\ge 0}

求解其 LP 松弛后，得到单纯形法的最终单纯形表。设当前基矩阵对应的非基变量为 xN1,…,xNmx_{N_1}, \dots, x_{N_m}，基本变量 xBix_{B_i} 可表示为：

xBi=βi−∑j∈NαijxNjx_{B_i} = \beta_i - \sum_{j \in N} \alpha_{ij} x_{N_j}

其中 βi\beta_i 为当前右侧常数项。若 βi\beta_i 非整数，记 βi=⌊βi⌋+fi\beta_i = \lfloor \beta_i \rfloor + f_i，其中 fi∈(0,1)f_i \in (0,1) 为小数部分。类似地，将系数分解为 αij=⌊αij⌋+fij\alpha_{ij} = \lfloor \alpha_{ij} \rfloor + f_{ij}。由于所有变量受整数约束，方程两端取小数部分后导出一个必要条件：

fi−∑j∈NfijxNj≤0f_i - \sum_{j \in N} f_{ij} x_{N_j} \le 0

等价地写作：

∑j∈NfijxNj≥fi\sum_{j \in N} f_{ij} x_{N_j} \ge f_i

这一不等式即为戈莫里割。它迫使当前非整数解不可行（因为当所有非基变量为零时，左侧为零，不等式 0≥fi>00 \ge f_i > 0 不成立），同时能被数学证明保留所有整数可行解。

计算步骤

割平面法的执行流程可以归纳为以下迭代步骤：

  1. 初始化：求解原整数规划问题的 LP 松弛（移除整数约束），得最优解 x∗\mathbf{x}^*。若 LP 松弛无可行解，则 IP 亦无可行解，终止。
  2. 检验整数性：若 x∗\mathbf{x}^* 的所有分量均为整数，则算法终止——该解即为 IP 的最优解。
  3. 生成割平面：选取某一基本变量 xBix_{B_i}，其当前 LP 解值 βi\beta_i 为非整数。利用单纯形表中该行的系数生成戈莫里割不等式。
  4. 添加割平面：将割平面作为新增约束加入当前的 LP 问题中，重新求解扩大后的 LP（通常采用对偶单纯形法高效处理）。
  5. 迭代：返回步骤 2，直至获得整数最优解或判定问题无界/无可行解。

生成割平面时，通常选择小数部分 fif_i 最大的基本变量对应的行，因为该行的割平面倾向于产生较深的割除效果，有助于加速收敛。这一启发式策略称为"最大分数规则"（maximum fractional rule）。

计算示例

考虑如下纯整数规划问题：

max⁡  x1+4x2s.t. 2x1+4x2≤7,5x1+3x2≤15,x1,x2≥0 且为整数\begin{aligned} \max \; & x_1 + 4x_2 \\ \text{s.t. } & 2x_1 + 4x_2 \le 7, \\ & 5x_1 + 3x_2 \le 15, \\ & x_1, x_2 \ge 0 \text{ 且为整数} \end{aligned}

首先求解 LP 松弛。用单纯形法解得最优解为 x1=1.5, x2=1.0x_1 = 1.5,\, x_2 = 1.0，目标值 Z=5.5Z = 5.5。由于 x1=1.5x_1 = 1.5 非整数，需要生成割平面。

在最终单纯形表中，基本变量 x1x_1 对应的行（非整数行）写为：

x1+0.0x3+0.1x4=1.5x_1 + 0.0x_3 + 0.1x_4 = 1.5

其中 x3,x4x_3, x_4 为松弛变量。取小数部分，f1=0.5f_{1} = 0.5，f13=0.0f_{13} = 0.0，f14=0.1f_{14} = 0.1。戈莫里割为：

0.1x4≥0.5⇒x4≥50.1x_4 \ge 0.5 \quad \Rightarrow \quad x_4 \ge 5

将 x4=15−5x1−3x2x_4 = 15 - 5x_1 - 3x_2 代入，还原至原始变量表述为：

5x1+3x2≤105x_1 + 3x_2 \le 10

将割平面加入原问题重新求解 LP，得到新解 x1=0.8, x2=1.5x_1 = 0.8,\, x_2 = 1.5。x2x_2 非整数，继续生成割平面，最终在若干次迭代后收敛到最优整数解 x1=0, x2=1x_1 = 0,\, x_2 = 1（或另一极点的整数解），验证即得 IP 最优解。

算法优势与局限

优势。割平面法的理论根基优雅且可靠——Gomory 证明了在纯整数规划情形下算法必在有穷步内终止于最优整数解（或判定不可行/无界），具有良好的有限收敛性。该方法与单纯形法和对偶单纯形法天然融合，易于在标准 LP 求解器框架内实现。

局限。在实践中，纯粹的割平面法存在一系列收敛速度问题。最突出的缺陷是慢尾效应（tailing-off）：随着大量割平面的累积，每轮新增割平面带来的目标值改善递减，收敛极为缓慢。割平面过密还会引发数值不稳定问题，使 LP 问题的规模迅速膨胀。此外，Chvátal 等学者证明，在某些问题族上所需的割平面数量呈指数增长。

分支割平面法

正是由于纯割平面法的上述局限，现代整数规划实践中极少单独使用割平面法。Ralph Gomory 方法的重大贡献在于启发了分支割平面法（Branch and Cut）——该混合框架将分支定界法与割平面法深度整合：在分支定界搜索树的每个节点上，先通过添加少量割平面收紧当前 LP 松弛的下界，再用分支操作细分可行域。割平面的引入大幅提升了定界效率，显著缩减分支规模。

分支割平面法已成为当今所有主流整数规划求解器（包括CPLEX、Gurobi、SCIP、GLPK 等）的核心算法引擎，融合了 Gomory 割、覆盖割（cover cuts）、混合整数割（MIR cuts）、lift-and-project 割等多种割平面家族。各求解器根据问题结构自适应选择最优割平面组合策略，在理论优雅性与工程实用性之间取得了成功的平衡。

变体与应用

割平面思想已远远超出了 Gomory 最初提出的纯整数规划范畴，衍生出丰富的变体系列：

  • 混合整数割平面：处理部分变量为整数、部分为连续的混合整数规划问题，通过修改 Gomory 割的推导条件使其适用于混合整数环境。
  • 非线性割平面：在凸优化中，对于非线性目标或约束的问题，每次迭代向当前解添加一个支撑超平面（梯度割或客观割），逐步逼近可行域——凯利割平面法（Kelley's cutting plane method）即为典型代表。
  • 最大割与组合优化中的应用：在最大割问题、旅行商问题等 NP-hard 组合优化问题中，割平面法被用于收紧半定规划松弛，生成更加紧凑的可行域描述。
  • 随机规划中的 Benders 分解：广义上，Benders 分解的可行性割与最优性割亦可视为割平面法在高维随机规划场景下的延伸形态。

割平面法的核心洞见——通过逐步生成约束来避免显式处理完整约束集合——已经发展成为大规模数学规划中"列生成"与"行生成"两类延迟生成策略之一（行生成），是运筹学中最具影响力的方法论创新之一。