# 干货 | 10分钟带你全面掌握branch and bound（分支定界）算法-概念篇

- New Arrival -

01 什么是branch and bound？

1.1

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.

The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.

1.2

02 原理解析

1) 首先从主问题分出两支子问题：

2) 从节点1和节点2两个子问题再次分支，得到如下结果：

3) 对节点5进行分支，得到：

4) 此时，所有的分支遍历都完成，我们最终找到了最优解。

03 算法框架

```1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
3. Loop until the queue is empty:
3.1. Take a node N off the queue.        3.2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x).        3.3. Else, branch on N to produce new nodes Ni. For each of these:
3.3.1. If bound(N_i) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.                3.3.2. Else, store Ni on the queue.```

Depth-first search (DFS)：深度优先搜索，就是纵向搜索，先一个分支走到底，再跳到另一个分支走到底。这种搜索可以用LIFO queue也就是栈实现。

Best-First Search：最佳优先搜索，最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。这种搜索可以用优先队列priority queue来实现。

04 伪代码描述[1]

`// C++-like implementation of branch and bound, // assuming the objective function f is to be minimizedCombinatorialSolution branch_and_bound_solve(    CombinatorialProblem problem,     ObjectiveFunction objective_function /*f*/,    BoundingFunction lower_bound_function /*g*/) {    // Step 1 above    double problem_upper_bound = std::numeric_limits<double>::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<CandidateSolutionTree> 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()) < problem_upper_bound) {                current_optimum = node.candidate();                problem_upper_bound = objective_function(current_optimum);            }            // else, node is a single candidate which is not optimum        }        else { // Step 3.3: node represents a branch of candidate solutions            // "child_branch" represents N_i above            for (auto&& child_branch : node.candidate_nodes) {                if (lower_bound_function(child_branch) <= problem_upper_bound) {                    candidate_queue.enqueue(child_branch); // Step 3.3.2                }                // otherwise, g(N_i) > B so we prune the branch; step 3.3.1            }        }    }    return current_optimum;}`

05 reference

[1] https://en.wikipedia.org/wiki/Branch_and_bound

[2] OR-Wayne Winston

END

0 条评论

• ### 干货 | 10分钟带你掌握branch and price（分支定价）算法超详细原理解析

相信大家对branch and price的神秘之处也非常好奇了。今天我们一起来揭秘该算法原理过程。

• ### 掌握branch and cut算法原理附带C++求解TSP问题代码

branch and cut其实还是和branch and bound脱离不了干系的。所以，在开始本节的学习之前，请大家还是要务必掌握branch and bo...

• ### 车辆路径规划中的Location-Routing Problem简介

今天为大家介绍的是选址-路径问题(Location-Routing Problem, LRP)，首先上目录

• ### 基于网络社交媒体活动行为的宣传影响力，推荐有影响力的目标 (CS IR)

在线社交媒体(Online Social Media，简称OSM)是一个平台，通过这个平台，用户可以在不同的内容上通过消息、发布、回应、标记、分享等社交活动向互...

• ### 伯克利大学计算机科学的大规模教学观（CS CY）

在过去的十年中，全国各地的计算机科学(CS)的本科招生人数呈爆炸式增长，因为计算机技能在许多领域中已被证明越来越重要。在这种前所未有的学生需求推动下，加州大学伯...

• ### Integration of Deep Learning and Neuroscience整合神经科学和深度学习

Neuroscience has focused on the detailed implementation of computation, studying...

• ### TiB、TB的区别

使用谷歌的单位转换，忽然糊涂了，对着Terabyte和Tebibyte, 知道应该是2进制和十进制的区别，单愣是不知道哪个应该是二进制。

• ### 论文记录 - ECG Heartbeat Classiﬁcation: A Deep Transferable Representation

这篇论文发自 2018 年，出自洛杉矶大学的一个团队，主要对 5 种不同心率进行预测分类及预测 MI（心肌梗死）。论文地址：https://arxiv.org/...

• ### Auto-Encoding GAN

Mihaela Rosca, Balaji Lakshminarayanan, David Warde-Farley, Shakir Mohamed

• ### 少数人的智慧:从个人行为预测集体的成功（Computers and Society）

我们能否通过监控一小群人的行为来预测一个产品、服务或业务未来的成功？一个积极的答案会对成功的科学和管理实践产生重要的影响，然而最近的研究却支持了截然相反的答案。...