分枝界限法

什么是分枝界限法

分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅游商困难，创当时的记录。“分枝界限法”把困难的可行解展开如树的分枝，再经由各个分枝中寻求最佳解^[1]。

分枝界限法也能够运用在混合整数规划困难上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割形成最靠近的两个整数，分列条件，加入原困难中，形成两个子困难(或分枝)分别求解，这样便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解^[2]。

分枝界限法的基本思想^[3]

1、基本思想

分枝定界法是一个用途十分大量的算法，运用该种算法的技巧性很强，不同类型的困难解法也各不相同。分支定界法的基本思想是对有约束条件的最优化困难的所有可行解（数目有限）空间执行搜索。该算法在具体实施时，把全部可行的解空间持续分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限多出已知可行解值那些子集不再做更深一步分支。如此，解的很多子集（即搜索树上的很多结点）就可以不予考虑了，进而缩减了搜索规模。这一过程一直执行到找出可行解为止，该可行解的值不大于任何子集的界限。所以该种算法一般可以求得最优解。

将困难分枝为子困难并对这些子困难定界的步骤称为分枝定界法。

2、分枝节点的选择

对搜索树上的某些点务必做出分枝决策，即凡是界限差于目前为止所有可行解最小下界的任何子集（节点），都有机会作为分枝的选择对象（对求最小值困难来说）。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：

1）从最小下界分枝（队列式FIFO分枝限界法）：每次算完界限后，把搜索树上目前所有叶节点的界限执行比较。找出限界最小的节点，此结点即为下次分枝的结点。

优点：检查子困难较少，能较快地求得最佳解；

缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。

2）从最新造成的最小下界分枝（优先队列式分枝限界法）：从最新造成的各子集中选择具有最小的下界的结点执行分枝。

优点：节省了空间；

缺点：需要较多的分枝运算，耗费的时间较多。

这两个原则更更深一步表明了，在算法设计中的时空转换概念。

分枝定界法已经成功地应用于求解整数规划困难、生产进程表困难、货郎担困难、选址困难、背包困难以及可行解的数目为有限的很多其它困难。对于不同的困难，分枝与界限的步骤和内容或许不同，但基本原理是一样的。

分枝界限法的步骤^[4]

分枝界限法是组合优化困难的有效求解方法，其步骤如下所述：

步骤一：假如困难的目标为最小化，则设定当前最优解的值Z=∞

步骤二：依据分枝法则（Branching rule），从仍未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。

步骤三：计算每一个新分枝出来的节点的下限值（Lower bound，LB）

步骤四：对每一节点执行洞悉条件试探，若节点满足够下任意一个条件，则此节点可洞悉而不再被考虑：

此节点的下限值大于等于Z值。

已寻到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，燕以此为可行解的值。

此节点不或许包含可行解。

步骤五：判定能否仍有仍未被洞悉的节点，假如有，则执行步骤二，假如已无仍未被洞悉的节点，则演算停止，并得到最优解。

Kolen等曾利用此方法求解含时间窗约束的车辆巡回困难，其实验的节点数规模为6-15。当节点数为6时，计算机演算所花费的时间大概1分钟（计算机型为VAZ11/785），当节点数扩大到12时，计算机有内存不足的现象造成，所以分枝定界法比较适用于求解小型困难。Held和Karp表示分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。

分枝界限法的算法实例^[3]

1、型推销员困难

设有5个城v₁,v₂,v₃,v₄,v₅ ,从某一城市出发，遍历各城市一次且仅一次，最后返回原地，求最短路径。其费用矩阵如下：

将矩阵D对角线以上的元素从小到大排列为：

d₁₃,d₁₅,d₂₄,d₄₅,d₃₄,d₃₅KKKK

取最小的5个求和得：d₁₃ + d₁₅ + d₂₄ + d₄₅ = 14

用表明，要组成一个回路，所以每个顶点的下标在回路的所有边中各显现两次。（1）中显然5显现了3次，若用d₃₅代替d₁5则d₁₃ + d₃₅ + d₂₄ + d₂₅ + d₄₅ = 21即

搜索过程可以表明如下图：

图（2）的下界为21，图（3）的下界为20，都大于19故没有更深一步搜索的价值，所以（5）为最佳路径：

2、型推销员困难

D = (d_ij)n ^* n即。不妨把D看成旅费，即从v_i到v_j的旅费与v_j到v_i不一样。

对D的每行减去该行的最小元素，或每列减去该列的最小元素，得一新矩阵，致使每行每列起码都有一个0元素。

第一列和第三列没有为0的元素，所以第一列和第三列分别减去其最小元素1和3得：

受于从任一v_i出发一次，进入v_i也是一次，所以困难等价于求

的最佳路径，下标45是预期的界，即旅费起码为45单位（每个点出发都去最小值）。

受于矩阵D第一行第四列元素为0，故从v₁出发的路径应选择v₁ %26minus; %26minus; v₄，为了消除v₁出发进入其余点和从其余点进入v₄的机会，并封锁v₄到v₁的路径，在矩阵中除却第一行和第四列，并将第四列第一行元素15改为∞。得：

相似的从v₂出的路径应选v₂ %26minus; %26minus; v₅，消第v₂行和第v₅列，并将第v₅行第v₂列元素改为∞得：

这时第二行没有0元素，减去最小元素3得：

搜索过程如下图：

最后得到最佳路径为：

分枝界限法的算法分析^[3]

1、算法优点：可以求得最优解、平均速度快。

由于从最小下界分支，每次算完限界后，把搜索树上目前所有的叶子结点的限界执行比较，找出限界最小的结点，此结点即为下次分支的结点。该种决策的优点是检查子困难较少，能较快的求得最佳解。

2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。

存在的困难：分支定界法可应用于大批组合优化困难。其要害技术在于各结点权值如何预期，可以说一个分支定界求解方法的效率差不多由值界方法决定，若界预期不好，在极端情形下将与穷举搜索没多大区别。

参考文献

↑ 邓宇佑(硕士).求解医院运输部门运输中心个数最佳化之研究

↑ 《作业研究》[M].第七章 整数规划

↑ ^3.03.13.2 分枝界限法

↑ 夏新海.物流配送车辆调度优化研究[D].武汉理工大学,2004年