Gomory 分数割

把系数拆成整数部分与分数部分，并把原行移项，可得

左边是整数，因此右边也是整数。令 $s=\sum _{j}f(a_j)x_j$；由于 $f(a_j)\ge 0$、$x_j\ge 0$，有 $s\ge 0$，而 $s-f(\beta )$ 是整数。既然 $0<f(\beta )<1$，$s$ 不可能落在 $[0,f(\beta ))$ 中，只能满足 $s\ge f(\beta )$。

这个推理有两根支柱：整数变量使分数余数只能按整步改变，非负变量阻止左侧落到负的一支。割并没有猜测某个未知整数最优解在哪里，而是对原行的全部整数解同时成立。

一行、一个分数基点、一条新边界 ​

取

当前基点为 $(x_B,x_1,x_2)=(3/2,0,0)$。分数割为

原行乘四后是 $4x_B+2x_1+x_2=6$。例如 $(x_B,x_1,x_2)=(1,1,0),(1,0,2),(0,3,0),(0,2,2),(0,1,4),(0,0,6)$ 都合法，并满足割。当前非基本原点 $(0,0)$ 却违反 $2x_1+x_2\ge 2$，所以重新求 LP 时不能再停在原分数基点。

这条割对当前行所允许的整数点有效，因而也对满足全部原约束的整数点有效。它可能没有描述完整整数包公理库整数多面体与整数包Integral polyhedron · Integer hull区分整数点、整数包和整数多面体，说明何时所有线性目标都能由整数解达到，以及无顶点情形为何需要额外小心。；排除一个基点之后，其他分数顶点仍可能留下。

负系数必须向下取整 ​

若某个 $a_j=-1/4$，其分数部分是

不是 $-1/4$，也不是零。向零截断会破坏 $f(a_j)\ge 0$，原证明的关键一步随之失效。实现中应使用数学 floor，尤其注意编程语言的整数除法在负数上的约定。

若 $f(\beta )>0$，却所有 $f(a_j)=0$，所得割是 $0\ge f(\beta )$，直接证明该行没有整数解。这不是一条“太强”的错误割，而是整数等式右端与左端的同余冲突。

连续变量为何不能照搬 ​

考虑 $x_B=3/2-(3/2)z$，其中 $x_B$ 要求非负整数，但 $z$ 允许非负实数。取 $z=1/3$，得到合法点 $x_B=1$。若误用纯整数分数割，会要求 $(1/2)z\ge 1/2$，即 $z\ge 1$，反而删掉这个合法点。

失效原因是 $\lfloor 3/2\rfloor z=z$ 不再是整数，前面的整数同余推理不能成立。混合整数问题需要 Gomory mixed-integer 或其他适配连续变量的割，不能仅把纯整数公式里的变量类型注释改掉。

一条含 $q$ 个非基本系数的行，提取割需要 $O(q)$ 次分数部分计算和写出操作；有理数的位成本另计。把割加入 LP 后还要重新优化，其成本不能记作这 $O(q)$ 的一部分。新割往往使当前基失去原始可行性，而可以利用对偶单纯形等方法重优化，具体仍取决于选取的标准型和基状态。

反复“选一行、加一刀”并不自动附带有限终止或多项式时间保证。Gomory 的有限算法需要规定选行、枢轴与防循环策略；只给出有效割公式，证明的是本次删点正确，而不是任意割序列都会快速到达整数最优。

LP 舍入公理库线性规划松弛与舍入LP relaxation and rounding放宽整数可行域获得可计算界，再把分数解舍入为可行组合解。把一个分数解送回整数可行域，并分析目标损失；这里保持全部整数可行点不变，收紧的是松弛域。Chvátal–Gomory 闭包公理库Chvátal–Gomory 割与闭包Chvátal–Gomory cut · CG closure · Chvátal rank用全部整数法向的支持值取整定义表示无关的闭包，并以精确四轮例子同时证明 Chvátal rank 的上界和下界。则把一整族有效取整割同时相交，研究多轮后还剩下什么几何区域。分支切割法公理库分支切割法与局部割作用域Branch and cut把有效割嵌入分支定界，在提高松弛上界的同时记录每条局部割的祖先作用域，交出可逐结点核验的最优证书。在搜索树中选择性加入这些割，还必须记录它们是否依赖当前分支条件。