整数规划的分支定界

回溯公理库回溯法Backtracking深度优先枚举部分解并在不可能完成时撤销选择的搜索范式。可以靠违反约束排除候选，分支定界还利用目标信息：即使某个区域仍含可行整数点，只要都不会比 incumbent 更好，就无须知道那些点具体在哪里。

正确性由两个不变量合在一起：所有尚未排除的整数方案仍位于活结点的并中；被关闭的结点或者没有整数方案，或者其全部方案的目标都不超过当前 $L$。分支保证没有漏掉整数点，上界保证关闭安全，incumbent 的原约束与整数可行性保证下界真实。

设活结点包括当前正在处理但尚未关闭的结点，且每个都持有有效上界。全局界为

孩子尚未求 LP 时可暂用父亲的上界。所有结点关闭且已有 incumbent 时，$U=L$，最优性得到认证；若全部关闭仍无整数可行解，则原问题不可行。

从 18.5 的松弛界走到整数最优 18 ​

考虑

根 LP 在 $(2,1/2)$ 达到 $37/2=18.5$。按分数坐标 $y$ 分支：

最后一个结点中 $3x+2y\ge 3\cdot 2+2\cdot 1=8>7$，没有任何可行点。所有叶子都关闭，得到最优值 $18$、解 $(1,2)$。

上界不是求解器报的一个数 ​

根结点的上界可直接用原不等式证书验证：把资源约束乘 $5/2$，把 $x\le 2$ 乘 $1/2$，相加就是

在 $y\ge 1$ 结点，把资源约束乘 $8/3$、$-y\le -1$ 乘 $1/3$，得到上界 $55/3$。在 $x\le 1$ 孩子中，用 $5/2$ 倍资源约束和 $1/2$ 倍 $x\le 1$，得到上界 $18$。各自都有同值可行 LP 点，所以既是上界，也是精确 LP 最优值。

不可行叶也有短证书：资源约束加 $3(-x\le -2)$、加 $2(-y\le -1)$，得出 $0\le -1$。读者无需重新运行 LP 求解器，就能检查这棵搜索树。

如果先探索右侧并得到整数解 18，再处理左侧 $y\le 0$，由 $x\le 2,y\le 0$ 已可知目标至多 16，直接界剪即可。搜索顺序改变了何时找到好解、需要解多少个 LP，却不改变任何关闭理由的有效性。

不能把松弛点当作 incumbent ​

根 LP 的 $(2,1/2)$ 不满足整数条件，不能把 $18.5$ 当作可行解下界。把它四舍五入到 $(2,1)$ 又违反资源约束，因此“先取整”也不自动给出 incumbent。任何启发式解都必须回代全部原约束并检查整数性，才有资格用于剪枝。

数值近似同样需要方向明确：最大化问题的一份原始 LP 可行点提供的是 LP 最优值下界，不能据它剪掉整数子树。用来剪枝的应是有效对偶上界，或带明确误差补偿的上界；一个很小的求解残差并不等于严格证书。

深度优先通常较快深入到整数叶，利于改善 incumbent；按最大上界优先可用优先队列公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。管理活结点，着重处理仍可能决定全局界的区域。变量选择、强分支和启发式会影响效率，但完整覆盖与可信界才决定正确性。

有限整数盒与严格分支保证搜索最终结束：沿任一路径，某个坐标的可选整数区间不断缩小，最终或者不可行，或者只剩一个整数赋值。候选赋值总数可达 $\prod _j(u_j-{\ell }_j+1)$，所以有限终止并不是多项式时间保证。运行成本还包括每个结点的 LP 求解、可行性传播、启发式和活结点存储，不能只按树深度报告。

若 $c$ 为整数且变量全为整数，上界还可安全向下取整。本例已有解 18 时，根界 $18.5$ 直接取整成 18 就能完成认证；上面的树保留未取整的 LP 界，是为了分别展示整数叶和不可行叶的证书。更强的松弛或合法取整可以减少搜索，而不改变逻辑框架。

分支切割法公理库分支切割法与局部割作用域Branch and cut把有效割嵌入分支定界，在提高松弛上界的同时记录每条局部割的祖先作用域，交出可逐结点核验的最优证书。进一步在结点中加入整数有效割，提高上界质量。它必须回答一个新的问题：这条割是对整个问题有效，还是只在当前祖先条件下有效？