Branch and bound
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 branchandbound 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.
Graph and tree search algorithms 

Listings 

Related topics 
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.
The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum[1][2] in 1960 for discrete programming, and has become the most commonly used tool for solving NPhard optimization problems.[3] The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem.[4][5]
Overview
The goal of a branchandbound algorithm is to find a value x that maximizes or minimizes the value of a realvalued function f(x), called an objective function, among some set S of admissible, or candidate solutions. The set S is called the search space, or feasible region. The rest of this section assumes that minimization of f(x) is desired; this assumption comes without loss of generality, since one can find the maximum value of f(x) by finding the minimum of g(x) = −f(x). A B&B algorithm operates according to two principles:
 It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching.
 Branching alone would amount to bruteforce enumeration of candidate solutions and testing them all. To improve on the performance of bruteforce search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find, and uses these bounds to "prune" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution.
Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such a representation is called an instance of the problem. Denote the set of candidate solutions of an instance I by S_{I}. The instance representation has to come with three operations:
 branch(I) produces two or more instances that each represent a subset of S_{I}. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, the optimal solution among S_{I} must be contained in at least one of the subsets.[6])
 bound(I) computes a lower bound on the value of any candidate solution in the space represented by I, that is, bound(I) ≤ f(x) for all x in S_{I}.
 solution(I) determines whether I represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among S_{I}.[6])
Using these operations, a B&B algorithm performs a topdown recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I, it checks whether bound(I) is greater than the lower bound for some other instance that it already visited; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum lower bound seen among all instances examined so far.
Generic version
The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function f.[3] To obtain an actual algorithm from this, one requires a bounding function g, that computes lower bounds of f on nodes of the search tree, as well as a problemspecific branching rule. As such, the generic algorithm presented here is a higher order function.
 Using a heuristic, find a solution x_{h} 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.
 Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
 Loop until the queue is empty:
 Take a node N off the queue.
 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).
 Else, branch on N to produce new nodes N_{i}. For each of these:
 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.
 Else, store N_{i} on the queue.
Several different queue data structures can be used. This FIFO queuebased implementation yields a breadthfirst search. A stack (LIFO queue) will yield a depthfirst algorithm. A bestfirst branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their lower bound.[3] Examples of bestfirst search algorithms with this premise are Dijkstra's algorithm and its descendant A* search. The depthfirst variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.[7]
Pseudocode
A C++like pseudocode implementation of the above is:
1 // C++like implementation of branch and bound,
2 // assuming the objective function f is to be minimized
3 CombinatorialSolution branch_and_bound_solve(
4 CombinatorialProblem problem,
5 ObjectiveFunction objective_function /*f*/,
6 BoundingFunction lower_bound_function /*g*/)
7 {
8 // Step 1 above
9 double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
10 CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
11 problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
12 CombinatorialSolution current_optimum = heuristic_solution;
13 // Step 2 above
14 queue<CandidateSolutionTree> candidate_queue;
15 // problemspecific queue initialization
16 candidate_queue = populate_candidates(problem);
17 while (!candidate_queue.empty()) { // Step 3 above
18 // Step 3.1
19 CandidateSolutionTree node = candidate_queue.pop();
20 // "node" represents N above
21 if (node.represents_single_candidate()) { // Step 3.2
22 if (objective_function(node.candidate()) < problem_upper_bound) {
23 current_optimum = node.candidate();
24 problem_upper_bound = objective_function(current_optimum);
25 }
26 // else, node is a single candidate which is not optimum
27 }
28 else { // Step 3.3: node represents a branch of candidate solutions
29 // "child_branch" represents N_i above
30 for (auto&& child_branch : node.candidate_nodes) {
31 if (lower_bound_function(child_branch) <= problem_upper_bound) {
32 candidate_queue.enqueue(child_branch); // Step 3.3.2
33 }
34 // otherwise, g(N_i) > B so we prune the branch; step 3.3.1
35 }
36 }
37 }
38 return current_optimum;
39 }
In the above pseudocode, the functions heuristic_solve
and populate_candidates
called as subroutines must be provided as applicable to the problem. The functions f (objective_function
) and g (lower_bound_function
) are treated as function objects as written, and could correspond to lambda expressions, function pointers or functors in the C++ programming language, among other types of callable objects.
Improvements
When is a vector of , branch and bound algorithms can be combined with interval analysis[8] and contractor techniques in order to provide guaranteed enclosures of the global minimum.[9][10]
Applications
This approach is used for a number of NPhard problems
 Integer programming
 Nonlinear programming
 Travelling salesman problem (TSP)[4][11]
 Quadratic assignment problem (QAP)
 Maximum satisfiability problem (MAXSAT)
 Nearest neighbor search[12] (by Keinosuke Fukunaga)
 Flow shop scheduling
 Cutting stock problem
 False noise analysis (FNA)
 Computational phylogenetics
 Set inversion
 Parameter estimation
 0/1 knapsack problem
 Feature selection in machine learning[13]
 Structured prediction in computer vision[14]^{:267–276}
Branchandbound may also be a base of various heuristics. For example, one may wish to stop branching when the gap between the upper and lower bounds becomes smaller than a certain threshold. This is used when the solution is "good enough for practical purposes" and can greatly reduce the computations required. This type of solution is particularly applicable when the cost function used is noisy or is the result of statistical estimates and so is not known precisely but rather only known to lie within a range of values with a specific probability.
Relation to other algorithms
Nau et al. present a generalization of branch and bound that also subsumes the A*, B* and alphabeta search algorithms from artificial intelligence.[15]
External links
See also
 Backtracking
 Branchandcut, a hybrid between branchandbound and the cutting plane methods that is used extensively for solving integer linear programs.
References
 A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. 28 (3). pp. 497–520. doi:10.2307/1910129.
 "Staff News". www.lse.ac.uk. Retrieved 20181008.
 Clausen, Jens (1999). Branch and Bound Algorithms—Principles and Examples (PDF) (Technical report). University of Copenhagen. Archived from the original (PDF) on 20150923. Retrieved 20140813.
 Little, John D. C.; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963). "An algorithm for the traveling salesman problem" (PDF). Operations Research. 11 (6): 972–989. doi:10.1287/opre.11.6.972.
 Balas, Egon; Toth, Paolo (1983). Branch and bound methods for the traveling salesman problem (PDF) (Report). Carnegie Mellon University Graduate School of Industrial Administration.
 Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Parallel Algorithm Design for Branch and Bound" (PDF). In Greenberg, H. J. (ed.). Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press.
 Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. p. 249.
 Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: PrenticeHall. ISBN 0134768531.
 Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1852332190.
 Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker.
 Conway, Richard Walter; Maxwell, William L.; Miller, Louis W. (2003). Theory of Scheduling. Courier Dover Publications. pp. 56–61.
 Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "A branch and bound algorithm for computing knearest neighbors". IEEE Transactions on Computers: 750–753. doi:10.1109/tc.1975.224297.
 Narendra, Patrenahalli M.; Fukunaga, K. (1977). "A branch and bound algorithm for feature subset selection" (PDF). IEEE Transactions on Computers. C26 (9): 917–922. doi:10.1109/TC.1977.1674939.
 Nowozin, Sebastian; Lampert, Christoph H. (2011). "Structured Learning and Prediction in Computer Vision". Foundations and Trends in Computer Graphics and Vision. 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651. doi:10.1561/0600000033. ISBN 9781601984579.
 Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "General branch and bound, and its relation to A∗ and AO∗" (PDF). Artificial Intelligence. 23 (1): 29–58. doi:10.1016/00043702(84)900043.