分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜寻与叠代的方法，选择不同的分支变数和子问题进行分支。
对于两个变数的整数规划问题，使用格线的方法有时更为简单。
通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
基本介绍
中文名 ：分支定界法 外文名 ：branch and bound 性质 ：算法 用途 ：整数规划问题求解 别称 ：分枝界限法
概述,基本思想,分枝节点的选择,步骤,算法分析,
概述
分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。 分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变数分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函式值的上限（上界）或下限（下界），从其中寻得最佳解。
基本思想
在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜寻树上的许多结点）就可以不予考虑了，从而缩小了搜寻范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。 将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。
分枝节点的选择
对搜寻树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。怎样选择搜寻树上的节点作为下次分枝的节点呢？有两个原则： 1）从最小下界分枝（优先伫列式分枝限界法）：每次算完界限后，把搜寻树上当前所有叶节点的界限进行比较。找出限界最小的节点，此结点即为下次分枝的结点。 ·优点：检查子问题较少，能较快地求得最佳解； ·缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多记忆体空间。 2）从最新产生的最小下界分枝（伫列式（FIFO）分枝限界法）：从最新产生的各子集中按顺序选择各结点进行分枝，对于下届比上届还大的节点不进行分枝。 优点：节省了空间；缺点：需要较多的分枝运算，耗费的时间较多。 这两个原则更进一步说明了，在算法设计中的时空转换概念。 分枝定界法已经成功地套用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。
步骤
分枝界限法是组合最佳化问题的有效求解方法，其步骤如下所述： 步骤一：如果问题的目标为最小化，则设定目前最优解的值Z=∞； 步骤二：根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点； 步骤三：计算每一个新分枝出来的节点的下限值（Lower bound，LB）； 步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑，此节点的下限值大于等于Z值。已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，以此为可行解的值。此节点不可能包含可行解； 步骤五：判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。 Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为6-15。当节点数为6时，计算机演算所花费的时间大约1分钟（计算机型为VAZ11/785），当节点数扩大至12时，计算机有记忆体不足的现象产生，所以分枝定界法比较适用于求解小型问题。Held和Karp指出分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。
算法分析
1、算法优点：可以求得最优解、平均速度快。 因为从最小下界分支，每次算完限界后，把搜寻树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。 2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多记忆体空间。 存在的问题：分支定界法可套用于大量组合最佳化问题。其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜寻没多大区别。