分支定界法

阐述

分支定界是一类求解离散优化的方法。它将解空间表达为一棵树，然后对这棵树进行完整的搜索。但是，在探索某一个分支之前，会先试图对这个分支所能给出的解的上界或者下界作出预判，从而减少不必要的搜索。例如：

• 对于最大化问题，找出分支的上界，如果上界小于已知的最好解，那么就不再搜索
• 对于最小化问题，找出分支的下界，如果下界大于已知的最好解，那么就不再搜索

形式上，设问题为 $\min c^Tx,x\in F$，则将其划分为几个子问题 $F_1,\cdots,F_k$，

1. 分支：选择一个子问题 $F_i$
2. 剪枝：如果子问题不可行，删除
3. 定界：计算出子问题的下界 $b(F_i)$
4. 剪枝：如果下界大于最优解，删除
5. 划分：如果下界小于最优解，继续划分为子问题

实例

用分支定界法求解背包问题的时候，一个合理的上界是把问题放松为线性规划（可以用贪婪法直接求解）时所得到的解。

一般的整数规划问题

1. 将问题放松为线性规划问题并求解
2. 如果差于最佳可行解，则剪枝
3. 如果线性规划的解是整数，那么得到了一个可行解
4. 如果线性规划的解不是整数，寻找一个非整数变量，然后求解 $x\le\lfloor f\rfloor$ 和 $x\ge\lceil f\rceil$ 的两个子问题
   1. 这个非整数变量常常是小数部分比较大的

从这个算法可以看出，放松为线性规划的时候必须能比较好地近似问题的最优解。

性质

相关内容

参考文献

• Branch and bound