分支割平面法

分支切割法（branch-and-cut）在分支定界搜索中动态加入有效不等式，以收紧整数规划的连续松弛。切割减少分数可行点，分支则把尚未解决的整数选择拆成互斥子问题；二者的共同要求是保留全部合法整数解，而非为了让图上区域变小就任意添加约束。

考虑三项两两冲突的任务，每项收益一。选择变量 $x_1,x_2,x_3\in \{0,1\}$，约束为 $$\begin{array}{cc}{x}_1+x_2& \le 1,x_1+x_3\le 1,\\ x_2+x_3& \le 1,max{x}_1+x_2+x_3.\end{array}$$ 合法整数方案最多选一项，最优值一。但连续松弛允许 $(1/2,1/2,1/2)$，目标为一点五。将三个约束相加得到总和不超过一点五，证明这一分数点就是松弛最优。

从整数逻辑得到有效切割

因为三项两两冲突，任意合法整数方案不能有两项同时为一，故都有 $$x_1+x_2+x_3\le 1.$$ 这条团不等式对全部整数方案有效，却排除了三个二分之一的分数点。加到松弛后，目标上界降为一，整数点 $(1,0,0)$ 又达到一，因此在根节点就证明了最优，无须继续分支。

两两冲突的图形揭示了原三行约束尚未充分表达的整数结构。被切去的是分数方案，而非任何合法整数选择。

有效性与分离是不同问题：前者要证明每个整数解都满足不等式，后者要找到当前分数解违反的某条有效不等式。不是每一条有效切割都能切掉当前点；也不是每一个切掉当前点的平面都有效。

搜索中的界与停止

以最大化问题为例，维护已找到的最佳整数收益 $L$。对一个节点，解加入有效切割后的松弛，得到上界 $U$。若节点不可行，或 $U\le L$，就可剪枝；若松弛最优点已是合法整数点，可更新 $L$ 并关闭该节点。否则可再分离切割，或挑一个分数整数变量作向下、向上取整的两个分支。

每次分支覆盖原节点全部整数可能；有效切割又不会删除这些整数可能，所以未被界证书剪掉的潜在最优解始终保留。所有节点都关闭时，当前整数方案与整体上界相合，才获得最优证书。若只因时间到了而停止，须报告已有方案与界的剩余差距，不能把可行解称为已证明最优。

一条仅在某个分支条件下成立的约束是局部切割。它不能未经证明就移到根节点，影响其他分支。例如在本例固定 $x_1=1$ 后可推出 $x_2=x_3=0$，但 $x_2=0$ 对根节点并非全局有效，因为 $(0,1,0)$ 本来合法。

精确核对本例的切割

这段独立小程序核验所有整数点上的切割有效性，再用有理数核对松弛界及改进后的证书；它不冒充通用整数规划求解器。

Python 3

from fractions import Fraction
from itertools import product

def triangle_cut_certificate():
    feasible = [x for x in product((0,1), repeat=3)
                if all(x[i]+x[j] <= 1 for i,j in [(0,1),(0,2),(1,2)])]
    if not all(sum(x) <= 1 for x in feasible):
        raise AssertionError("invalid cut")
    fractional = (Fraction(1,2),)*3
    old_upper = Fraction(3,2)  # add the three original inequalities, divide by2
    assert sum(fractional) == old_upper
    new_upper = 1  # the objective is exactly the cut's left side
    integer_value = max(sum(x) for x in feasible)
    assert integer_value == new_upper
    return old_upper, new_upper, len(feasible)

print(triangle_cut_certificate())
# (Fraction(3, 2), 1, 4)

三变量只有八个二元点，核验完全穷尽；若推广这种枚举到 $n$ 个变量，一般需指数时间，不能替代结构化的切割证明。变式。 若第三对不冲突，删去 $x_2+x_3\le 1$，方案 $(0,1,1)$ 变为合法、收益二；原团切割会错删它，因而不可继续使用。切割公式的来源是实际冲突关系，而非某种固定模板。