“Gomory 分数割可以由当前 LP tableau 生成;CG 取整可以从原约束与分支约束的合法组合生成。若组合用到了局部分支行,默认得到的就是局部割,除非另有证明把它提升为全局有效形式。”
形式陈述
单纯形法已经求出 LP 最优基,但某个应当取整数的基本变量却是分数。能否只看这一行,就自动构造一条保留全部整数解、却切掉当前基点的不等式?
考虑纯整数标准型:所有基本与非基本变量都要求非负整数。若原模型含整数系数不等式和整数右端,其松弛变量也必须一并视为整数变量。设当前一行写成
定义分数部分
所有系数从精确的有理 tableau 行计算。公式中的
当前基点令所有非基本变量为零,割左侧为零,右侧严格为正,所以必被切除。与此同时,原行的每个非负整数解都满足此割。
直觉
把系数拆成整数部分与分数部分,并把原行移项,可得
左边是整数,因此右边也是整数。令
这个推理有两根支柱:整数变量使分数余数只能按整步改变,非负变量阻止左侧落到负的一支。割并没有猜测某个未知整数最优解在哪里,而是对原行的全部整数解同时成立。
例子与边界
一行、一个分数基点、一条新边界
取
当前基点为
原行乘四后是
这条割对当前行所允许的整数点有效,因而也对满足全部原约束的整数点有效。它可能没有描述完整整数包;排除一个基点之后,其他分数顶点仍可能留下。
负系数必须向下取整
若某个
不是
若
连续变量为何不能照搬
考虑
失效原因是
推论与应用
一条含
反复“选一行、加一刀”并不自动附带有限终止或多项式时间保证。Gomory 的有限算法需要规定选行、枢轴与防循环策略;只给出有效割公式,证明的是本次删点正确,而不是任意割序列都会快速到达整数最优。
LP 舍入把一个分数解送回整数可行域,并分析目标损失;这里保持全部整数可行点不变,收紧的是松弛域。Chvátal–Gomory 闭包则把一整族有效取整割同时相交,研究多轮后还剩下什么几何区域。分支切割法在搜索树中选择性加入这些割,还必须记录它们是否依赖当前分支条件。
参考资料
- Ralph E. Gomory, “Outline of an Algorithm for Integer Solutions to Linear Programs”, Bulletin of the American Mathematical Society 64(5), 1958, pp. 275–278,尤其 pp. 276–277 的分数行构造和有效性证明:原论文副本。
- Ricardo Fukasawa, “Gomory Cuts”, 2010 encyclopedia author proof, pp. 1–2, “Gomory’s Fractional Cuts”:作者稿。非负纯整数条件、分数部分推导以及与混合整数割的区别。