分支定界的LP松弛上界

设 $x \in \mathbb{Z}^n_{\ge 0}$ 为整数可行集,$x \in \mathbb{R}^n_{\ge 0}$ 为同一约束 $Ax \le b$ 下(更大的)LP松弛可行集。由于去掉整数条件只是减少了约束,每个整数可行点也是LP可行的,因此整数可行集是LP松弛可行集的子集。

由于两个问题最大化同一个线性目标函数 $c^T x$,且整数规划的可行集包含于LP松弛的可行集之中,在较小集合上能达到的最优值不可能超过在较大集合上能达到的最优值。因此LP松弛的最优值是ILP最优值的一个上界。

分支定界法通过在当前LP松弛解中选取一个取分数值的变量,构造分别添加 $x_1 \le 1$ 或 $x_1 \ge 2$ 的两个子问题来建立搜索树;每个整数可行点恰好满足这两个条件之一,因此这一划分不会丢失任何整数解,反复划分也会持续无遗漏地分割空间。

在每个节点上,求解该子问题的LP松弛,按照上面同样的论证应用于更小的约束集,就得到了该节点之下所有仍可到达的整数解的一个上界。如果这个上界不大于目前在树中任何地方找到的最佳整数解的值,那么该节点的任何后代都不可能改进当前最佳解,因此可以剪掉整个子树,同时仍保证真正的最优解会在树的其他地方被找到。