# Branch and bound

Template:Graph search algorithm
**Branch and bound** (**BB** or **B&B**) is an algorithm design paradigm for discrete and combinatorial optimization problems. 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 method was first proposed by A. H. Land and A. G. Doig^{[1]} in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems.^{[2]} The name "branch and bound" first occurred in the work of Little *et al.* on the traveling salesman problem.^{[3]}^{[4]}

## Overview

In order to facilitate a concrete description, we assume that the goal is to find the *minimum* value of a function , where ranges over some set of *admissible* or *candidate solutions* (the *search space* or *feasible region*). Note that one can find the *maximum* value of by finding the minimum of . (For example, could be the set of all possible trip schedules for a bus fleet, and could be the expected revenue for schedule .)

A branch-and-bound procedure requires two tools. The first one is a *splitting* procedure that, given a set of candidates, returns two or more smaller sets whose union covers . Note that the minimum of over is , where each is the minimum of within . This step is called **branching**, since its recursive application defines a *search tree* whose *nodes* are the subsets of .

The second tool is a procedure that computes upper and lower bounds for the minimum value of within a given subset of . This step is called **bounding**.

The key idea of the BB algorithm is: if the *lower* bound for some tree node (set of candidates) is greater than the *upper* bound for some other node , then may be safely discarded from the search. This step is called **pruning**, and is usually implemented by maintaining a global variable (shared among all nodes of the tree) that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than can be discarded.

The recursion stops when the current candidate set is reduced to a single element, or when the upper bound for set matches the lower bound. Either way, any element of will be a minimum of the function within .

When is a vector of , branch and bound algorithms can be combined with interval analysis^{[5]}
and contractor techniques in
order to provide guaranteed enclosures of the global minimum.^{[6]}^{[7]}

### Generic version

The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function Template:Mvar.^{[2]} To obtain an actual algorithm from this, one requires a bounding function Template:Mvar, that computes lower bounds of Template:Mvar on nodes of the search tree, as well as a problem-specific branching rule.

- Using a heuristic, find a solution Template:Mvar to the optimization problem. Store its value,
*B*=*f*(*x*). (If no heuristic is available, set Template:Mvar to infinity.) Template:Mvar will denote the best solution found so far, and will be used as an upper bound on candidate solutions._{h} - 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 Template:Mvar off the queue.
- If Template:Mvar represents a single candidate solution Template:Mvar and
*f*(*x*) <*B*, then Template:Mvar is the best solution so far. Record it and set*B*←*f*(*x*). - Else,
*branch*on Template:Mvar to produce new nodes Template:Mvar. For each of these:

- If
*g*(*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 Template:Mvar on the queue.

- If

Several different queue data structures can be used. A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their Template:Mvar-value.^{[2]} The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.^{[8]}

## Applications

This approach is used for a number of NP-hard problems

- Integer programming
- Nonlinear programming
- Travelling salesman problem (TSP)
^{[3]}^{[9]} - Quadratic assignment problem (QAP)
- Maximum satisfiability problem (MAX-SAT)
- Nearest neighbor search (NNS)
- Cutting stock problem
- False noise analysis (FNA)
- Computational phylogenetics
- Set inversion
- Parameter estimation
- 0/1 knapsack problem
- Feature selection in machine learning
^{[10]} - [[k-nearest neighbor algorithm|Template:Mvar-nearest neighbor search]]
^{[11]} - Structured prediction in computer vision
^{[12]}^{:267–276}

Branch-and-bound 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.

## See also

- Alpha-beta pruning
- Backtracking
- Branch-and-cut, a hybrid between branch-and-bound and the cutting plane methods that is used extensively for solving integer linear programs.

## References

- ↑ Template:Cite article
- ↑
^{2.0}^{2.1}^{2.2}Template:Cite techreport - ↑
^{3.0}^{3.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ Template:Cite report
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Cite doi
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Cite doi