Chvátal–Gomory 割与闭包

从乘子表述到表示无关的支持值 ​

对整数方向 $c$，令

并只考虑此值有限的方向。闭包也可写成

这是只依赖集合 $P$ 的表达。LP 强对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。说明它与乘子表达相同：任意满足 $A^{\mathsf{T}}\lambda =c,\lambda \ge 0$ 的乘子都给出 ${\lambda }^{\mathsf{T}}b\ge h_P(c)$，所以对应取整割不会强于支持值取整；反过来，有限支持值存在一个最优对偶乘子，使两者恰好相等。因此改变约束缩放、添加冗余行，不会改变全部 CG 割的交。

例如 $x\le 1/2$ 与 $2x\le 1$ 的逐行右端取整结果不同，但完整闭包都包含 $x\le 0$：第二份表示只需用乘子 $1/2$。不变的是全部合法乘子的闭包，不是机械地把眼前每一行的右端 floor 一遍。

一轮不是“一刀” ​

一轮允许使用当前多面体的任意有效线性不等式，再做一次整数取整；新割可以在下一轮成为新的有效几何信息。一份证明里写了四条不等式，不意味着 rank 是四；这些不等式可能同属第一轮，也可能分属不同轮。

有理闭包的有限表示可借助TDI公理库全对偶整数性Total dual integrality · TDI要求每个整数目标都有整数的最优对偶证书，说明这一性质为何依赖不等式表示，以及整数右端如何传递原问题整数性。看出机制：给 $P$ 选择一份整数左端的有限 TDI 描述 $Bx\le d$，则 $P^{(1)}=\{x:Bx\le \lfloor d\rfloor \}$。因为任意整数目标的最优对偶可取整数 $y\ge 0$，若 $Bx\le \lfloor d\rfloor$，就有 $c^{\mathsf{T}}x\le y^{\mathsf{T}}\lfloor d\rfloor \le \lfloor y^{\mathsf{T}}d\rfloor$。这是有限描述存在的证明机制，并未声称高效找到该 TDI 描述。

一个 rank 恰为四的三角形 ​

令

它可写成 $0\le x\le 1$、$0\le y\le 4x$、$y\le 4-4x$。唯一整数点是 $(0,0),(1,0)$，整数包就是底边。下面先给四轮足够的证书，再证明三轮还不够。

第一轮。 两个整数方向 $(1,1)$、$(-1,1)$ 的支持值分别为 $5/2,3/2$，所以加入

相加得到 $y\le 3/2$。第二轮再对整数方向 $(0,1)$ 取整，得到 $y\le 1$。

此时闭包包含在原三角形与 $y\le 1$ 的交中。在这个较大的外包络上，$x+y$ 的最大值为 $7/4$，$-x+y$ 的最大值为 $3/4$。因此第三轮可分别推出

从而 $y\le 1/2$。第四轮对 $y$ 再取整，得到 $y\le 0$，与原来的 $y\ge 0$ 合起来，恰剩整数底边。于是 rank 至多为四。这里使用外包络支持值已经足够证明割有效，不要求这些少量割恰好列出了中间的全部闭包面。

下界必须挡住所有可能的割 ​

只展示自己选择的四轮切法，不能排除别人用更聪明的方向一轮完成。为证明下界，令

其中 $h\ge 1/2$ 是半整数。证明 $T_h^{(1)}$ 至少包含 $T_{h-1/2}$。两个整数底点当然保留，只需检查新顶点 $q=(1/2,h-1/2)$ 满足所有整数方向割。

任取 $(a,b)\in {\mathbb{Z}}^2$。若 $b\le 0$，则 $(a,b)\cdot q\le max(0,a)$，右侧是两个整数底点给出的整数支持值，故通过所有对应取整界。若 $b\ge 1$，原顶点给出的值 $a/2+bh$ 是整数或半整数，而 $q$ 的值比它少 $b/2\ge 1/2$。原支持值

也只能是整数或半整数，故 $q$ 的目标值不超过 $\lfloor H\rfloor$。两种情况覆盖全部整数法向量，引理成立。

闭包对包含关系单调：$Q\subseteq P$ 时 $Q^{(1)}\subseteq P^{(1)}$，因为 $h_Q(c)\le h_P(c)$。从 $T_2$ 反复应用引理，前三轮分别仍包含

这些点都在整数底边之外，所以 rank 至少四。与上界相遇，得到 rank 恰为四。脚本会对有界范围内的整数法向做额外数值核验，但真正覆盖无限多方向的是上述奇偶与分数部分论证。

整数左端不是可省略的形式条件 ​

不等式 $\frac{1}{2}x\le \frac{1}{2}$ 对整数点 $x=1$ 有效。若保持左端不变、擅自把右端取整成零，就会删掉它。必须先让最终左端系数为整数，才能推出左边只取整数值。本页三角形中所有割方向都显式是整数向量。

有限 rank 定理并不意味着少量轮数，也不意味着一轮闭包可以低成本完整生成。TDI 表述给出的有限面数可能很大，寻找最强的当前割也需要分离计算。逐次选择某些割的实际求解器，只维护整个闭包的外近似，不能把一次分离没有找到割说成已经完成全部闭包。

本页闭包依赖的是集合的全部有效不等式。相比之下，切割平面证明系统公理库切割平面证明系统Cutting planes proof system · CP proof system用布尔变量上的整数线性不等式、非负组合和整数取整导出矛盾的证明系统。关心一条有限推导的规则、长度与系数位数；证明长度不是闭包 rank。Gomory 分数割公理库Gomory 分数割Gomory fractional cut从纯整数单纯形表的一行提取分数部分，用非负性和整数同余推出一条排除当前分数基点的有效割。给出从当前 tableau 提取具体割的办法，而分支切割法公理库分支切割法与局部割作用域Branch and cut把有效割嵌入分支定界，在提高松弛上界的同时记录每条局部割的祖先作用域，交出可逐结点核验的最优证书。将有效割与搜索树结合。三者分别强调一条割的构造、全体割的几何效果，以及优化搜索中的使用方式。