割平面法

字数 3221 2025-10-26 19:16:22

割平面法

基本思想与动机
想象一下你在解决一个整数规划问题，比如要求变量只能取0或1（如是否投资某个项目）或者整数（如需要多少辆卡车）。但直接求解整数规划通常非常困难。一个常见的思路是：先暂时“忽略”整数限制，求解它的“线性规划松弛”问题（即允许变量取小数）。这个方法求解起来很快，但得到的解（比如需要3.6辆卡车）往往不满足整数要求，没有实际意义。

割平面法的核心思想就是：既然松弛问题的解不满足整数条件，我们就设法把那个“分数解”从可行域里“割”掉。 具体来说，我们为原来的松弛问题添加一个新的线性约束条件（即一条“切割平面”），这个新约束有两个关键作用：
- 它必须“切掉”当前这个我们不想要的分数解。
- 它不能“误伤”任何一个原本整数规划问题的可行整数解。
添加这个新约束后，我们重新求解这个更新后的线性规划问题。得到的新解可能仍然是分数解，那么我们就继续添加新的切割平面，一步步地将可行域中不包含整数解的“多余”部分切除，直到最终找到整数最优解。
核心构造：Gomory割
最早的、也是最经典的割平面是由Ralph Gomory提出的，因此称为Gomory割。我们来看它是如何从单纯形表的最终表中构造出来的。

假设我们求解整数规划的线性规划松弛后，得到了一个最优解，但其中一个本应为整数的变量 \(x_B\) 却是一个分数值。这个 \(x_B\) 在单纯形表中对应一个约束方程，我们把这个方程写出来：

\(x_B + \sum_{j \in N} a_{ij} x_j = b_i\)

其中，\(x_B\) 是基变量，\(x_j\) 是非基变量，\(b_i\) 是当前解中 \(x_B\) 的值（是一个分数）。

**构造步骤：**

a. 分离整数与小数部分：将方程中每一个系数 \(a_{ij}\) 和右端项 \(b_i\) 都“拆开”，写成“整数部分 + 小数部分”的形式，其中小数部分在 [0, 1) 区间内。
即：\(a_{ij} = \lfloor a_{ij} \rfloor + f_{ij}\)， \(b_i = \lfloor b_i \rfloor + f_i\)。
（例如，2.7 = 2 + 0.7， -1.3 = -2 + 0.7）

b. **重写方程**：将拆开后的式子代回原约束方程：

\(x_B + \sum_{j \in N} (\lfloor a_{ij} \rfloor + f_{ij}) x_j = \lfloor b_i \rfloor + f_i\)

c. **移项整理**：将所有整数项移到等式右边，分数项留在左边：

\(x_B + \sum_{j \in N} \lfloor a_{ij} \rfloor x_j - \lfloor b_i \rfloor = f_i - \sum_{j \in N} f_{ij} x_j\)

d. 推导不等式：观察上述等式。左边（\(x_B + \sum \lfloor a_{ij} \rfloor x_j - \lfloor b_i \rfloor\)）必须是一个整数，因为所有变量和 \(\lfloor \cdot \rfloor\) 都是整数。因此，等式右边（\(f_i - \sum f_{ij} x_j\)）也必须是一个整数。
同时，由于在当前的松弛解中，所有非基变量 \(x_j = 0\)，所以右边等于 \(f_i\)（一个大于0小于1的正分数）。但是，当我们寻求整数解时，非基变量可能会变化。为了保证右边始终是整数，它不能仅仅等于 \(f_i\)，它可以是 ...-2, -1, 0, 1, 2...。
然而，因为 \(f_i < 1\) 且 \(f_{ij} \ge 0\)，所以右边 \(f_i - \sum f_{ij} x_j\) 的最大可能值就是 \(f_i\)（当所有 \(x_j=0\)），它小于1。同时，因为它必须是整数，所以它只可能取 ≤ 0 的整数值。
因此，我们得到一个必然成立的约束：\(f_i - \sum_{j \in N} f_{ij} x_j \le 0\)

这个不等式 \(\sum_{j \in N} f_{ij} x_j \ge f_i\) 就是 Gomory割。它巧妙地利用了整数性要求，推导出了一个所有整数解都必须满足、但当前分数解不满足（因为当 \(x_j=0\) 时，左边=0，右边=f_i>0，不等式不成立）的线性约束。

算法流程与实例
让我们通过一个简化的例子来走一遍流程。考虑问题：
最大化 \(P = x + y\)
满足：
\(2x + y \le 5\)
\(-4x + 4y \le 5\)
\(x, y \ge 0\)，且为整数。

步骤1：求解线性规划松弛。
引入松弛变量 \(s1, s2\)，问题变为：
\(2x + y + s1 = 5\)
\(-4x + 4y + s2 = 5\)
最大化 \(P = x + y\)

求解这个线性规划（过程略），得到最优解为：
\(x = 1.25, y = 2.5, P = 3.75\)
这不是整数解。

步骤2：选择一行生成Gomory割。
我们选择y所在的行（因为y=2.5的小数部分0.5较大）。从单纯形表中，假设y行的方程为：
\(y + 0.5s1 + 0.25s2 = 2.5\)

步骤3：构造Gomory割。
- 分离小数部分：所有系数的小数部分都是正数。
  \(f_i = 0.5\)（来自2.5）
  \(f_{ij}\)：对于s1是0.5，对于s2是0.25。

写出割平面不等式：\(\sum f_{ij} x_j \ge f_i\)，即：
\(0.5s1 + 0.25s2 \ge 0.5\)
为了将其加入问题，我们引入一个非负的剩余变量 \(a1\)（称为人工变量或割变量）：
\(0.5s1 + 0.25s2 - a1 = 0.5\)

步骤4：将新约束加入问题并重新求解。
现在我们有三个等式约束。用对偶单纯形法求解这个新的线性规划。新的最优解是：
\(x = 1.5, y = 2, P = 3.5\)
x=1.5仍然不是整数。

步骤5：继续生成割平面。
我们选择x所在的行生成新的割平面。过程同上。添加新的割平面后，再次求解。最终，经过几轮迭代，我们会得到整数最优解：
\(x = 1, y = 2, P = 3\)
或者 \(x=2, y=1, P=3\)。

方法评价与进阶讨论
- 优点：
  - 概念优美：理论上是完备的，只要能求解线性规划，就一定能通过有限步切割找到整数规划的最优解（尽管步数可能非常多）。
  - 与分支定界法结合：纯割平面法在实际中可能收敛很慢。现代整数规划求解器（如CPLEX, Gurobi）通常将割平面法与强大的分支定界法结合使用，称为分支切割法。在分支定界树的每个节点上，不仅通过分支来划分问题，还通过生成各种割平面来收紧线性规划松弛的界限，从而极大地加速求解过程。
  - 多种割平面：除了Gomory割，还有针对特定问题结构的大量其他割平面，如覆盖割、背包割、GUB割等，它们能更有效地利用问题结构。
- 缺点与挑战：
  - 收敛速度：早期纯Gomory割法可能因为添加的约束太多、太“弱”而导致问题规模膨胀，求解缓慢，甚至出现数值不稳定。
  - 割平面的选择：生成哪个割平面、生成多少，是一个重要的策略问题，直接影响效率。
  - 数值稳定性：反复切割可能导致约束矩阵的性质恶化，产生数值计算上的困难。
总之，割平面法是整数规划求解工具箱中一项基础而强大的技术，它通过系统性地改进问题表述来逼近最优解，是现代商用优化求解器的核心组件之一。

割平面法基本思想与动机想象一下你在解决一个整数规划问题，比如要求变量只能取0或1（如是否投资某个项目）或者整数（如需要多少辆卡车）。但直接求解整数规划通常非常困难。一个常见的思路是：先暂时“忽略”整数限制，求解它的“线性规划松弛”问题（即允许变量取小数）。这个方法求解起来很快，但得到的解（比如需要3.6辆卡车）往往不满足整数要求，没有实际意义。割平面法的核心思想就是：既然松弛问题的解不满足整数条件，我们就设法把那个“分数解”从可行域里“割”掉。具体来说，我们为原来的松弛问题添加一个新的线性约束条件（即一条“切割平面”），这个新约束有两个关键作用：它必须“切掉”当前这个我们不想要的分数解。它不能“误伤”任何一个原本整数规划问题的可行整数解。添加这个新约束后，我们重新求解这个更新后的线性规划问题。得到的新解可能仍然是分数解，那么我们就继续添加新的切割平面，一步步地将可行域中不包含整数解的“多余”部分切除，直到最终找到整数最优解。核心构造：Gomory割最早的、也是最经典的割平面是由Ralph Gomory提出的，因此称为Gomory割。我们来看它是如何从单纯形表的最终表中构造出来的。假设我们求解整数规划的线性规划松弛后，得到了一个最优解，但其中一个本应为整数的变量 \(x_ B\) 却是一个分数值。这个 \(x_ B\) 在单纯形表中对应一个约束方程，我们把这个方程写出来： \(x_ B + \sum_ {j \in N} a_ {ij} x_ j = b_ i\) 其中，\(x_ B\) 是基变量，\(x_ j\) 是非基变量，\(b_ i\) 是当前解中 \(x_ B\) 的值（是一个分数）。构造步骤： a. 分离整数与小数部分：将方程中每一个系数 \(a_ {ij}\) 和右端项 \(b_ i\) 都“拆开”，写成“整数部分 + 小数部分”的形式，其中小数部分在 [ 0, 1) 区间内。即：\(a_ {ij} = \lfloor a_ {ij} \rfloor + f_ {ij}\)， \(b_ i = \lfloor b_ i \rfloor + f_ i\)。（例如，2.7 = 2 + 0.7， -1.3 = -2 + 0.7） b. 重写方程：将拆开后的式子代回原约束方程： \(x_ B + \sum_ {j \in N} (\lfloor a_ {ij} \rfloor + f_ {ij}) x_ j = \lfloor b_ i \rfloor + f_ i\) c. 移项整理：将所有整数项移到等式右边，分数项留在左边： \(x_ B + \sum_ {j \in N} \lfloor a_ {ij} \rfloor x_ j - \lfloor b_ i \rfloor = f_ i - \sum_ {j \in N} f_ {ij} x_ j\) d. 推导不等式：观察上述等式。左边（\(x_ B + \sum \lfloor a_ {ij} \rfloor x_ j - \lfloor b_ i \rfloor\)）必须是一个整数，因为所有变量和 \(\lfloor \cdot \rfloor\) 都是整数。因此，等式右边（\(f_ i - \sum f_ {ij} x_ j\)）也必须是一个整数。同时，由于在当前的松弛解中，所有非基变量 \(x_ j = 0\)，所以右边等于 \(f_ i\)（一个大于0小于1的正分数）。但是，当我们寻求整数解时，非基变量可能会变化。为了保证右边始终是整数，它不能仅仅等于 \(f_ i\)，它可以是 ...-2, -1, 0, 1, 2...。然而，因为 \(f_ i < 1\) 且 \(f_ {ij} \ge 0\)，所以右边 \(f_ i - \sum f_ {ij} x_ j\) 的最大可能值就是 \(f_ i\)（当所有 \(x_ j=0\)），它小于1。同时，因为它必须是整数，所以它只可能取 ≤ 0 的整数值。因此，我们得到一个必然成立的约束：\(f_ i - \sum_ {j \in N} f_ {ij} x_ j \le 0\) 这个不等式 \(\sum_ {j \in N} f_ {ij} x_ j \ge f_ i\) 就是 Gomory割。它巧妙地利用了整数性要求，推导出了一个所有整数解都必须满足、但当前分数解不满足（因为当 \(x_ j=0\) 时，左边=0，右边=f_ i>0，不等式不成立）的线性约束。算法流程与实例让我们通过一个简化的例子来走一遍流程。考虑问题：最大化 \(P = x + y\) 满足： \(2x + y \le 5\) \(-4x + 4y \le 5\) \(x, y \ge 0\)，且为整数。步骤1：求解线性规划松弛。引入松弛变量 \(s1, s2\)，问题变为： \(2x + y + s1 = 5\) \(-4x + 4y + s2 = 5\) 最大化 \(P = x + y\) 求解这个线性规划（过程略），得到最优解为： \(x = 1.25, y = 2.5, P = 3.75\) 这不是整数解。步骤2：选择一行生成Gomory割。我们选择y所在的行（因为y=2.5的小数部分0.5较大）。从单纯形表中，假设y行的方程为： \(y + 0.5s1 + 0.25s2 = 2.5\) 步骤3：构造Gomory割。分离小数部分：所有系数的小数部分都是正数。 \(f_ i = 0.5\)（来自2.5） \(f_ {ij}\)：对于s1是0.5，对于s2是0.25。写出割平面不等式：\(\sum f_ {ij} x_ j \ge f_ i\)，即： \(0.5s1 + 0.25s2 \ge 0.5\) 为了将其加入问题，我们引入一个非负的剩余变量 \(a1\)（称为人工变量或割变量）： \(0.5s1 + 0.25s2 - a1 = 0.5\) 步骤4：将新约束加入问题并重新求解。现在我们有三个等式约束。用对偶单纯形法求解这个新的线性规划。新的最优解是： \(x = 1.5, y = 2, P = 3.5\) x=1.5仍然不是整数。步骤5：继续生成割平面。我们选择x所在的行生成新的割平面。过程同上。添加新的割平面后，再次求解。最终，经过几轮迭代，我们会得到整数最优解： \(x = 1, y = 2, P = 3\) 或者 \(x=2, y=1, P=3\)。方法评价与进阶讨论优点：概念优美：理论上是完备的，只要能求解线性规划，就一定能通过有限步切割找到整数规划的最优解（尽管步数可能非常多）。与分支定界法结合：纯割平面法在实际中可能收敛很慢。现代整数规划求解器（如CPLEX, Gurobi）通常将割平面法与强大的分支定界法结合使用，称为分支切割法。在分支定界树的每个节点上，不仅通过分支来划分问题，还通过生成各种割平面来收紧线性规划松弛的界限，从而极大地加速求解过程。多种割平面：除了Gomory割，还有针对特定问题结构的大量其他割平面，如覆盖割、背包割、GUB割等，它们能更有效地利用问题结构。缺点与挑战：收敛速度：早期纯Gomory割法可能因为添加的约束太多、太“弱”而导致问题规模膨胀，求解缓慢，甚至出现数值不稳定。割平面的选择：生成哪个割平面、生成多少，是一个重要的策略问题，直接影响效率。数值稳定性：反复切割可能导致约束矩阵的性质恶化，产生数值计算上的困难。总之，割平面法是整数规划求解工具箱中一项基础而强大的技术，它通过系统性地改进问题表述来逼近最优解，是现代商用优化求解器的核心组件之一。