分支切割法与局部割作用域

分支把候选分成两个盒子，切割则在一个盒子里用整数结构削去多余分数区域。两者可以交替：先用便宜的全局割改进根松弛，遇到仍然分数的解再分支，随后利用分支已经确定的信息推导更强的局部割。

局部条件是证明的一部分。例如“在 $x_0=0$ 的结点中，变量 $x_2$ 必须为零”可以完全正确，却不能省略前半句，把 $x_2\le 0$ 塞回全局模型。算法不仅要维护不等式的系数，还要记住这些系数是在什么条件下成立的。

Gomory 分数割公理库Gomory 分数割Gomory fractional cut从纯整数单纯形表的一行提取分数部分，用非负性和整数同余推出一条排除当前分数基点的有效割。可以由当前 LP tableau 生成；CG 取整公理库Chvátal–Gomory 割与闭包Chvátal–Gomory cut · CG closure · Chvátal rank用全部整数法向的支持值取整定义表示无关的闭包，并以精确四轮例子同时证明 Chvátal rank 的上界和下界。可以从原约束与分支约束的合法组合生成。若组合用到了局部分支行，默认得到的就是局部割，除非另有证明把它提升为全局有效形式。

五项设备选择与一条条件容量 ​

选择五件设备，变量 $x_0,\dots ,x_4\in \{0,1\}$。五圈相邻设备冲突：

另外设备 2 的容量需求为二，基础容量为一，启用设备 0 可再增加二：

最大化收益

非负性与五圈度约束已隐含 $x_i\le 1$，放松后无需另写重复上界。根 LP 在全一半向量处达到 $16$。把五条冲突约束按循环次序乘 $(1,4,4,3,4)$ 相加，左边恰为目标，右边为 $16$，得到一份同值上界证书。

全局奇圈割收紧根，但还没有解完 ​

把五条冲突约束各乘 $1/2$ 相加，得到 $\sum _i{x}_i\le 5/2$。对整数解取整，加入全局割

新 LP 最优点为

这次的对偶证书公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。可以直接写成：$13/2$ 倍奇圈割，加 $3/4$ 倍容量约束，加 $1/2$ 倍 $x_3+x_4\le 1$，再加 $3/2$ 倍 $-x_1\le 0$。相加后左边正好是 $z$，右边为 $13+3/4+1/2=57/4$。它说明新解不只是某个分数可行点，而确实达到当前松弛上界。

左支的局部取整 ​

按分数变量 $x_0=1/4$ 分支。左支加入 $x_0\le 0$，结合非负性即 $x_0=0$。其 LP 最优点可取 $(0,1/2,1/2,0,1)$，值为 $27/2$。

在此结点，将容量约束乘 $1/2$，再加一次分支行 $x_0\le 0$，得到 $x_2\le 1/2$。由于 $x_2$ 是整数，推出局部割 $x_2\le 0$。加入后，LP 在整数点 $(0,1,0,0,1)$ 达到 $12$。上界由

认证，其中最后一项用到了局部割。得到 incumbent 12，这个结点可以关闭。

右支给出唯一最优解 ​

右支加入 $x_0\ge 1$，于是 $x_0=1$，相邻冲突迫使 $x_1=x_4=0$，余下 $x_2+x_3\le 1$。所以

在 $(1,0,1,0,0)$ 达到。更新 incumbent 为 $13$，右支也关闭。根的两支已经完整覆盖整数方案，左界 12、右界 13 与可行解 13 相遇，全局最优得到证明。

若把左支的 $x_2\le 0$ 错当成全局割，恰好会删掉这个唯一最优点。错误模型最多只得 $12$，因此作用域错误不仅改变搜索效率，还会输出错误最优值。

局部割可以怎样提升 ​

本例的原容量约束其实还直接给出一个全局 CG 割：除二后左端 $x_2-x_0$ 已是整数表达式，所以

保留 $x_0$ 项，就得到全局有效的 $x_2\le x_0$；只在左支 $x_0=0$ 时，才可把它简化成 $x_2\le 0$。这展示了提升局部结论时应补回哪一部分条件。根节点若选择这个全局割，会得到另一棵搜索树；前面的执行只选择奇圈割后分支，并没有声称完成整个 CG 闭包或使用了最少结点。

算法保证与实际成本 ​

每条割的有效性保证整数候选没有被误删；分支的完整性保证尚未解决的整数点仍由活结点覆盖；可行 incumbent 与对偶上界保证剪枝安全。三份证书同时成立，才能继承分支定界的精确最优性。

若在一个结点无限加割却永不分支，有限搜索域本身不能保证整个过程终止。一个简单可证明终止的策略是每结点只做有限轮分离，然后在仍分数时分支；有限整数界保证最终搜索树有限。实际成本需累计分离、重新解 LP、割管理、可行解搜索及结点处理，没有一般多项式时间保证。

删掉一条不再活跃的有效割可以让 LP 松弛变弱，但不会使原整数可行点丢失；反之，错误地跨作用域使用局部割会破坏正确性。求解器的全局割池与本地分离存储因此不能被视为仅仅两种缓存位置。

单元任务：把计划与最优性证书一起交付 ​

先把四乘四双随机计划

分解为三份置换排班，证明每轮匹配存在、权重和为一、逐项重构，并解释分配 LP 的整数性为什么来自 TU，而不只是这份示例。

然后复算本页五项选择模型。交付根与每个孩子的原始 LP 点、对偶上界、整数 incumbent、每条割的乘子与作用域。最终报告应为：根界 $16$，加奇圈割后 $57/4$，左支 $27/2$ 经局部割降至 $12$，右支整数最优 $13$；错误全局复用局部割会误报 $12$。

最后对 $\mathrm{conv}\{(0,0),(1,0),(1/2,2)\}$，同时给四轮 CG 上界割与前三轮保留点，证明 rank 恰为四。禁止把有限条测试法向都通过，当作无限法向下界的替代。

下载完整题解、精确有理核验脚本、逐结点与逐轮结果。脚本使用标准库分数算术，通过小规模顶点枚举寻找 LP 点，再独立核对非负对偶乘子及目标相等；它是可复核的教学实现，不以生产整数求解器的性能为目标。