分支定界（，BB）是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法，但是和穷举法所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。
该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的，目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。
概述
分支定界法的目的是从可行解集合S中选出一个解x，使得目标函数f(x)最大化或最小化。其中集合S被称为搜寻空间或可行区域。本节所有的最佳化问题均可视为对f(x)进行最小化，因为对f(x)进行最大化问题本质上还是对g(x)=-f(x)进行最小化。分支定界法需要遵循以下两个原则：
*先是将搜寻空间通过递归的手段分成多个子空间，在每个子空间对f(x)进行最小化，这种分割方式就是分支。
*如果只有分支那么这种方法就成为了暴力搜索法，运算量将会非常庞大。为了提升算法的性能，需要对每个分支进行下界计算，对于那些下界已经超过目前最佳解的分支，需要进行剪枝操作。
为了将这些原则转化为问题的具体算法，我们需要将这些候选解转化为合适的数据结构，这样的表示方式被称为问题的实例。我们用S_I表示实例I的候选解集，实例表示必须有如下三个操作:
*branch(I)：产生两个或多个实例，每个实例为S_I的一个子集。（通常来讲，每个子集都是互不相交的，这是为了避免每个候选解被多次访问从而浪费时间，但有时也会有例外。S_I的最优解必然会出现在它的一个或多个子集中。）
*bound(I)：计算实例I中所有候选解所对应的目标函数值的下界，满足对于任意x \in S_I，bound(I) \leq f(x)。
*solution(I)：确定I是否表示单个候选解。（如果不是，接下来可以从S_I中回传一些可行的解再进一步进行分支定界的操作。）如果solution(I)回传了一个解，那么f(solution(I))提供了整个可行解空间中最优目标函数的上界。
通过使用这些操作，分支定界算法在分支操作形成的实例树中执行自顶向下递归搜索。在访问实例I时，我们不妨先检查bound(I)，如果bound(I)已经大于目前所找到的上界，我们就直接丢弃该实例。为了实现这一步骤，我们需要设定一个全局变量，用于记录目前为止所检查的所有实例中看到的最小上界。
通用格式
下面是最小化任意目标函数f的通用分支定界算法框架。
伪代码
和C++语言相似的伪代码如下：
// C++-like implementation of branch and bound,
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
CombinatorialProblem problem,
ObjectiveFunction objective_function /f/,
BoundingFunction lower_bound_function /bound/)
{
// Step 1 above
double problem_upper_bound = std::numeric_limits::infinity; // = B
CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
CombinatorialSolution current_optimum = heuristic_solution;
// Step 2 above
queue candidate_queue;
// problem-specific queue initialization
candidate_queue = populate_candidates(problem);
while (!candidate_queue.empty()) { // Step 3 above
// Step 3.1
CandidateSolutionTree node = candidate_queue.pop();
// "node" represents N above
if (node.represents_single_candidate()) { // Step 3.2
if (objective_function(node.candidate()) B so we prune the branch; step 3.3.1
}
}
}
return current_optimum;
}
在上述伪代码中，函数heuristic_solve和populate_candidates为子程序，必须基于具体问题进行设计。
改进
当\mathbf{x}为空间处于\mathbb{R}^n的向量时，分支定界算法可以与区间分析和间隔承包商技术相结合，以提供全局最小包络值的保证。
参考文献
评论 (0)