概念

割平面法

不断添加 Gomory 割、覆盖割等线性不等式割去松弛解而不切掉整数点，收紧可行域直至得到整数解。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

割平面法运筹学

01定义

割平面法不断向线性松弛添加有效不等式（割），割去松弛的非整数最优点却不切掉任何整数可行点，逐步把松弛多面体「削」成整数点的凸包——Gomory 割从单纯形表代数生成，无需枚举。

割平面：一刀刀削去松弛解，保全整数点

从单纯形表的分数行出发： $\sum_j(f_{ij})x_j\geq f_{i0}$ （ $f$ 为小数部分）——纯代数生成，理论上有限步达到整数最优；实践中单独使用收敛慢。

覆盖割、MIR 割、流覆盖割利用问题结构，效果远超通用割；专用割（如 TSP 的子回路消除割）是求解组合难题的关键知识注入。

割太多使 LP 变慢、太少收效甚微：求解器按「违背程度 × 正交性」筛选割池，定期清理冗余割——割的选择本身是一门调参艺术。

\sum_{j}\,f_{ij}\,x_j\geq f_{i0},\quad f_{ij}=a_{ij}-\lfloor a_{ij}\rfloor\ (\text{Gomory 分数割})

戈莫里 1958 年发明割平面法——首个整数规划的纯代数精确算法；长期被认为不实用，1990 年代与分支定界结合后重获新生。

混合整数规划的商用求解器内核、TSP 竞赛级求解（Concorde）、排产与网络设计、组合优化的多面体研究。

Gomory 割：切掉分数 LP 最优解分数最优解不是整数解：加一条割平面把它切出可行域，重新求解

步骤0