前言

- New Arrival -

 

之前一直做启发式算法，最近突然对精确算法感兴趣了。但是这玩意儿说实话是真的难，刚好boss又叫我学学column generation求解VRP相关的内容。

 

一看里面有好多知识需要重新把握，所以这段 时间就打算好好学学精确算法。届时会把学习过程记录下来，也方便大家学习！

 

01 什么是branch and bound？

 

 

1.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 原理解析

 

为了让大家更好理解分支定界的原理，这里小编举一个求解整数规划的例子来给大家演示分支定界算法的具体过程。

 

首先，对于一个整数规划模型：

 

 

因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。

 

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

 

 

通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头。继续往下。

 

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

 

 

 

子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。

 

子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10，那么从该支下去找到的解也不会变得更好，所以剪掉！

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

 

 

子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4<当前的BestV=10，所以不更新BestV，同时该支下去也不能得到更好的解了。

 

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

 

 

03 算法框架

 

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。

 

上面用了求解整数规划的例子，这虽然有助于我们更好理解这个算法，但是针对整数规划这一特定问题的过程描述，有可能会对我们的思维带来局限性。而不能更好的理解该算法的精髓。

 

所以小编决定，在这一节里面，将一个更通用的算法框架呈现出来，以便大家能更好的了解分支定界算法的真正精髓所在。

 

假设我们求的是最小化问题 minimize f(x)。branch and bound的过程可以描述如下：[1]

 

•  

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.

 

 

其实代码该过程描述也很明了了。第1步可以用启发式找一个当前最优解B出来，如果不想也可以将B设置为正无穷。对于一个最小化问题而言，肯定是子问题的lower bound不能超过当前最优解，不然超过了，该子问题就需要剪掉了。

 

第2第3步主要是用队列取构建一个搜索树进行搜索，具体的搜索方式由queue这个数据结构决定的。

 

前面我们讲了，B&B是围绕着一颗搜索树进行的，那么对于一棵树而言就有很多种搜索方式：

 

 

Breadth-first search (BFS)：广度优先搜索，就是横向搜索，先搜索同层的节点。再一层一层往下。这种搜索可以用FIFO queue实现。

 

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

 

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

 

04 伪代码描述[1]

 

按照上述框架的过程，下面提供了一个很详细的C++伪代码：

 

•  

// 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;}

 

有了伪代码加持，相信大家对上面的过程以及branch and bound 算法也有了一个透彻的了解。后面我们还会推出关于branch and bound的相关代码实现，包括各种数据结构实现的各种搜索方式等等，请关注我们的公众号以获取最新的消息：

 

 

05 reference

 

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

[2] OR-Wayne Winston

 

END