分枝界限法是由三栖学者理查德·卡普(Richard M.Karp)在20世纪60年代发明,成功求解含有65个城市的旅行商问题,创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝,再经由各个分枝中寻找最佳解。
分枝界限法也能够使用在混合整数规划问题上,其为一种系统化的解法,以一般线性规划之单形法解得最佳解后,将非整数值之决策变量分割成为最接近的两个整数,分列条件,加入原问题中,形成两个子问题(或分枝)分别求解,如此便可求得目标函数值的上限(上界)或下限(下界),从其中寻得最佳解。
在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支。这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
对搜索树上的某些点必须作出分枝决策,即凡是界限小于迄今为止所有可行解最小下界的任何子集(节点),都有可能作为分枝的选择对象(对求最小值问题而言)。怎样选择搜索树上的节点作为下次分枝的节点呢?有两个原则:
1)从最小下界分枝(优先队列式分枝限界法):每次算完界限后,把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点,此结点即为下次分枝的结点。
·优点:检查子问题较少,能较快地求得最佳解;
·缺点:要存储很多叶节点的界限及对应的耗费矩阵,花费很多内存空间。
2)从最新产生的最小下界分枝(队列式(FIFO)分枝限界法):从最新产生的各子集中按顺序选择各结点进行分枝,对于下届比上届还大的节点不进行分枝。
优点:节省了空间;缺点:需要较多的分枝运算,耗费的时间较多。
这两个原则更进一步说明了,在算法设计中的时空转换概念。
分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题,分枝与界限的步骤和内容可能不同,但基本原理是一样的。
分枝界限法是组合优化问题的有效求解方法,其步骤如下所述:
步骤一:如果问题的目标为最小化,则设定最优解的值Z=∞;