Branch and bound

Branch and bound (BB or B&B) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.

The method was first proposed by A. H. Land and A. G. Doig[1] in 1960 for discrete programming.
General description

For definiteness, we assume that the goal is to find the minimum value of a function f(x), where x ranges over some set S of admissible or candidate solutions (the search space or feasible region). Note that one can find the maximum value of f(x) by finding the minimum of g(x) = -f(x). (For example, S could be the set of all possible trip schedules for a bus fleet, and f(x) could be the expected revenue for schedule x.)

A branch-and-bound procedure requires two tools. The first one is a splitting procedure that, given a set S of candidates, returns two or more smaller sets \( S_1, S_2, \ldots \) whose union covers S. Note that the minimum of f(x) over S is \( \min\{v_1, v_2, \ldots\} \) , where each \( v_i \) is the minimum of f(x) within \( S_i \) . This step is called branching, since its recursive application defines a tree structure (the search tree) whose nodes are the subsets of S.

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

The key idea of the BB algorithm is: if the lower bound for some tree node (set of candidates) A is greater than the upper bound for some other node B, then A may be safely discarded from the search. This step is called pruning, and is usually implemented by maintaining a global variable m (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 m can be discarded.

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

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

Knapsack problem
Integer programming
Nonlinear programming
Traveling salesman problem (TSP)
Quadratic assignment problem (QAP)
Maximum satisfiability problem (MAX-SAT)
Nearest neighbor search (NNS)
Cutting stock problem
False noise analysis (FNA)

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. An example of its application here is in biology when performing cladistic analysis to evaluate evolutionary relationships between organisms, where the data sets are often impractically large without heuristics[citation needed].

For this reason, branch-and-bound techniques are often used in game tree search algorithms, most notably through the use of alpha-beta pruning.

Branch-and-bound applications in combinatorial data analysis, Michael J. Brusco, Stephanie Stahl

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.


.