Branch and bound

Template:Short description Branch-and-bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller subproblems and using a bounding function to eliminate subproblems that cannot contain the optimal solution.

It 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, then 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 in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem.

Overview

The goal of a branch-and-bound algorithm is to find a value Template:Mvar that maximizes or minimizes the value of a real-valued function Template:Math, called an objective function, among some set Template:Mvar of admissible or candidate solutions. The set Template:Mvar is called the search space, or feasible region. The rest of this section assumes that minimization of Template:Math is desired; this assumption comes without loss of generality, since one can find the maximum value of Template:Math by finding the minimum of Template:Math. A B&B algorithm operates according to two principles:

• It recursively splits the search space into smaller spaces, then minimizes Template:Math on these smaller spaces; the splitting is called branching.
• Branching alone would amount to brute-force enumeration of candidate solutions and testing them all. To improve on the performance of brute-force 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 Template:Mvar by Template:Mvar. The instance representation has to come with three operations:

• Template:Math produces two or more instances that each represent a subset of Template:Mvar. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among Template:Mvar must be contained in at least one of the subsets.)
• Template:Math computes a lower bound on the value of any candidate solution in the space represented by Template:Mvar, that is, Template:Math for all Template:Mvar in Template:Mvar.
• Template:Math determines whether Template:Mvar represents a single candidate solution. (Optionally, if it does not, then the operation may choose to return some feasible solution from among Template:Mvar.Template:R) If Template:Math returns a solution, then Template:Math provides an upper bound for the optimal objective value over the whole space of feasible solutions.

Using these operations, a B&B algorithm performs a top-down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance Template:Mvar, it checks whether Template:Math is equal to or greater than the current upper bound; if so, Template:Mvar 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 upper 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 Template:Mvar. To obtain an actual algorithm from this, one requires a bounding function Template:Math, that computes lower bounds of Template:Mvar on nodes of the search tree, as well as a problem-specific branching rule.

1. Using a heuristic, find a solution Template:Mvar to the optimization problem. Store its value, Template:Math. (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.
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:
   1. Take a node Template:Mvar off the queue.
   2. If Template:Mvar represents a single candidate solution Template:Mvar and Template:Math, then Template:Mvar is the best solution so far. Record it and set Template:Math.
   3. Else, branch on Template:Mvar to produce new nodes Template:Mvar. Add all nodes for which Template:Math to the queue. The remaining nodes, having a lower bound greater than or equal to the upper bound of the problem, will never lead to the optimal solution and are discarded.

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 lower bounds. 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.

Improvements

When $𝐱$ is a vector of ${ℝ}^n$, branch-and-bound algorithms can be combined with interval analysis and contractor techniques to provide guaranteed enclosures of the global minimum.

Applications

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

• Integer programming
• Nonlinear programming
• Travelling salesman problem (TSP)
• Quadratic assignment problem (QAP)
• Maximum satisfiability problem (MAX-SAT)
• Nearest neighbor search (by Keinosuke Fukunaga)
• Flow shop scheduling
• Cutting stock problem
• Computational phylogenetics
• Set inversion
• Parameter estimation
• 0/1 knapsack problem
• Set cover problem
• Feature selection in machine learning
• Structured prediction in computer visionTemplate:Rp
• Arc routing problem, including the Chinese Postman problem
• Talent Scheduling, scenes-shooting arrangement problem

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.Template:Citation needed

Relation to other algorithms

Nau et al. present a generalization of branch and bound that also subsumes the A*, B* and alpha-beta search algorithms.

Optimization example

Branch-and-bound can be used to maximize $Z=5x_1+6x_2$ with the constraints

$x_1+x_2\le 50$

$4x_1+7x_2\le 280$

$x_1,x_2\ge 0$

$x_1$ and $x_2$ are integers.

The first step is to relax the integer constraint. We have two extreme points for the first equation that form a line: $\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}50\\ 0\end{array}\right]$ and $\left[\begin{array}{c}0\\ 50\end{array}\right]$. We can form the second line with the vector points $\left[\begin{array}{c}0\\ 40\end{array}\right]$ and $\left[\begin{array}{c}70\\ 0\end{array}\right]$.

the two lines.

The third point is $\left[\begin{array}{c}0\\ 0\end{array}\right]$. This is a convex hull region, so the solution lies on one of the vertices of the region. We can find the intersection using row reduction, which is $\left[\begin{array}{c}70/3\\ 80/3\end{array}\right]$ with a value of 276 + 2/3. We test the other endpoints by sweeping the line over the region and find this is the maximum over the reals.

We choose the variable with the maximum fractional part, in this case $x_2$ becomes the parameter for the branch and bound method. We branch to $x_2\le 26$ and obtain 276 at $⟨24,26⟩$. We have reached an integer solution so we move to the other branch $x_2\ge 27$. We obtain 275.75 at $⟨22.75,27⟩$. We have a decimal, so we branch $x_1$ to $x_1\le 22$ and we find 274.571 at $⟨22,27.4286⟩$. We try the other branch $x_1\ge 23$ and there are no feasible solutions. Therefore, the maximum is 276 with $x_1=24$ and $x_2=26$.

See also

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

External links

• Cbc – (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.