割平面法的理解

割平面法的理解

1. 简介

割平面法（Cutting Plane Method）用于求解整数规划问题，通过逐步添加线性约束（割平面）逼近整数解。本文以Gomory割平面法为例，结合简单示例拆解核心步骤。

---

2. 示例详解

问题描述

考虑整数规划问题：
$$\begin{array}{rl}\max & 3x_1+2x_2\\ \text{s.t.}& 2x_1+x_2\le 6\\ & 2x_1+3x_2\le 9\\ & x_1,x_2\ge 0,\text{且为整数}\end{array}$$

步骤1：求解松弛问题

引入松弛变量 $x_3,x_4\ge 0$，转化为标准LP问题：
$$\begin{array}{rl}\max & 3x_1+2x_2\\ \text{s.t.}& 2x_1+x_2+x_3=6\\ & 2x_1+3x_2+x_4=9\\ & x_1,x_2,x_3,x_4\ge 0\end{array}$$
用单纯形法求解得：$x_1=1.5,x_2=2,x_3=0,x_4=0$，目标值8.5。

步骤2：选择非整数基变量

• 基变量：$x_1,x_2$（非整数解）。
• 约束方程：选择非整数基变量（如 $x_1$）对应的约束方程。
  单纯形表中，$x_1$ 的约束方程为：
  $$x_1+0.5x_3-0.5x_4=1.5\text{（来自行变换后的约束1，由非基变量表示基变量的变换而得）}$$

步骤3：构造割平面

1. 分解系数和常数项

   将系数和常数项分解为整数部分（向下取整）和小数部分（小数部分 $f\in [0,1)$）：
   $$\begin{array}{rlr}0.5& =0+0.5& \text{(系数}{x}_3\text{)}\\ -0.5& =-1+0.5& \text{(系数}{x}_4\text{)}\\ 1.5& =1+0.5& \text{(常数项)}\end{array}$$

2. 分离整数与小数部分
   原方程改写为：
   $$\underset{\text{整数部分}}{\underbrace{x_1-x_4-1}}+\underset{\text{小数部分}}{\underbrace{0.5x_3+0.5x_4=0.5}}$$

3. 生成割平面约束
   由于左边小数部分必须补偿右边的0.5，且变量非负：
   $$0.5x_3+0.5x_4\ge 0.5\Rightarrow x_3+x_4\ge 1$$

   • 每个系数的小数部分 $<1$，导致它们的线性组合可以 ≥1，不过并不影响上述不等式的成立。

步骤4：添加割平面并重新求解

将新约束转换为等式（引入松弛变量 $x_5\ge 0$）：
$$x_3+x_4-x_5=1$$
重新求解LP，得到整数解：$x_1=1,x_2=2$，目标值7。

---

3. 泛化公式

对任意整数规划问题，假设松弛问题最优解中某基变量 $x_i$ 非整数，其约束方程为：
$$x_i+\sum _{j\in N}{\bar{a}}_{ij}{x}_j={\bar{b}}_i$$
其中 $N$ 为非基变量集合，${\bar{b}}_i$ 非整数。

割平面构造流程

1. 分解系数：
   $${\bar{a}}_{ij}=\lfloor {\bar{a}}_{ij}\rfloor +f_{ij},{\bar{b}}_i=\lfloor {\bar{b}}_i\rfloor +f_i$$
   其中 $0\le f_{ij}<1$，$0<f_i<1$。

2. 分离方程：
   $$\underset{\text{整数部分}}{\underbrace{x_i+\sum _{j\in N}\lfloor {\bar{a}}_{ij}\rfloor x_j-\lfloor {\bar{b}}_i\rfloor }}+\underset{\text{小数部分}}{\underbrace{\sum _{j\in N}{f}_{ij}{x}_j-f_i=0}}$$

3. 生成割平面：
   由于小数部分必须非负：
   $$\sum _{j\in N}{f}_{ij}{x}_j\ge f_i$$

---

4. 关键细节

为什么割平面不切割整数解？

对任意整数可行解 $x_j$（包括松弛变量）：

1. 变量非负性：$x_j\ge 0$ 且为整数。
2. 系数分解规则：$f_{ij}\in [0,1)$，$f_i\in (0,1)$。

假设存在整数解不满足割平面约束：
$$\sum f_{ij}{x}_j<f_i$$
根据原约束方程分解形式：
$$\text{整数部分}+\sum f_{ij}{x}_j=f_i$$
左边整数部分必须为整数，右边 $f_i\in (0,1)$。若 $\sum f_{ij}{x}_j<f_i$，则：
$$\sum f_{ij}{x}_j=f_i-k(k\text{为正整数})$$
又因为$f_i\in (0,1)$：
$$\sum f_{ij}{x}_j=f_i-k<0$$
与 $x_j\ge 0$ 和 $f_{ij}\ge 0$ 矛盾！因此，任何整数解必须满足：
$$\sum f_{ij}{x}_j\ge f_i$$

收敛性

• 每次割平面至少切割当前非整数解，理论上有限步收敛，但实际中可能较慢，可嵌入分支定界法提升效率。

---