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 minimized CombinatorialSolution 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; }
