Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution.
It is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
design paradigm for
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
* Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
* Discrete group, ...
and
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
problems, as well as
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of
state space search
State-space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or ''states'' of an instance are considered, with the intention of finding a ''goal state'' with the ...
: the set of candidate solutions is thought of as forming a
rooted tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equi ...
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, 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
The London School of Economics and Political Science (LSE), established in 1895, is a public research university in London, England, and a member institution of the University of London. The school specialises in the social sciences. Founded ...
sponsored by
British Petroleum
BP p.l.c. (formerly The British Petroleum Company p.l.c. and BP Amoco p.l.c.; stylised in all lowercase) is a British multinational oil and gas company headquartered in London, England. It is one of the oil and gas " supermajors" and one of ...
in 1960 for
discrete programming,
and has become the most commonly used tool for solving
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
optimization problems.
The name "branch and bound" first occurred in the work of Little ''et al.'' on the
traveling salesman problem
In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...
.
Overview
The goal of a branch-and-bound algorithm is to find a value that maximizes or minimizes the value of a
real-valued function
In mathematics, a real-valued function is a function whose values are real numbers. In other words, it is a function that assigns a real number to each member of its domain.
Real-valued functions of a real variable (commonly called ''real ...
, called an
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
, among some set of admissible, or
candidate solution
In mathematical optimization and computer science, a feasible region, feasible set, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, ...
s. The set is called the search space, or
feasible region
In mathematical optimization and computer science, a feasible region, feasible set, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, ...
. The rest of this section assumes that minimization of is desired; this assumption comes
without loss of generality
''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...
, since one can find the maximum value of by finding the minimum of . A B&B algorithm operates according to two principles:
* It
recursively
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
splits the search space into smaller spaces, then minimizing 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
A prune is a dried plum, most commonly from the European plum (''Prunus domestica'') tree. Not all plum species or varieties can be dried into prunes. Use of the term ''prune'' for fresh plums is obsolete except when applied to varieties of ...
" 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
In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
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 by . The instance representation has to come with three operations:
* produces two or more instances that each represent a subset of . (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 must be contained in at least one of the subsets.
)
* computes a lower bound on the value of any candidate solution in the space represented by , that is, for all in .
* determines whether represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among .) If returns a solution then 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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
of instances formed by the branch operation. Upon visiting an instance , it checks whether is equal or greater than the current upper bound; if so, may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a
global variable
In computer programming, a global variable is a variable with global scope, meaning that it is visible (hence accessible) throughout the program, unless shadowed. The set of all global variables is known as the ''global environment'' or ''global ...
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 .
To obtain an actual algorithm from this, one requires a bounding function , that computes lower bounds of on nodes of the
search tree
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and les ...
, as well as a problem-specific branching rule. As such, the generic algorithm presented here is a
higher-order function In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:
* takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
.
# Using a
heuristic
A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
, find a solution to the optimization problem. Store its value, . (If no heuristic is available, set to infinity.) 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
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
* Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines ...
off the queue.
## If represents a single candidate solution and , then is the best solution so far. Record it and set .
## Else, ''branch'' on to produce new nodes . For each of these:
### If , 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 on the queue.
Several different
queue data structures
In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functi ...
can be used. This
FIFO queue-based implementation yields a
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...
. A
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
(LIFO queue) will yield a
depth-first
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...
algorithm. A
best-first branch and bound algorithm can be obtained by using a
priority queue
In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type.
In a priority queue, each element has an associated ''priority'', which ...
that sorts nodes on their lower bound.
Examples of best-first search algorithms with this premise are
Dijkstra's algorithm
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
and its descendant
A* search
A* (pronounced "A-star") is a graph traversal and pathfinding algorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algor ...
. 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.
Pseudocode
A
C++-like pseudocode implementation of the above is:
// 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 /*bound*/)
In the above pseudocode, the functions
heuristic_solve
and
populate_candidates
called as subroutines must be provided as applicable to the problem. The functions (
objective_function
) and (
lower_bound_function
) are treated as
function object
In computer programming, a function object is a construct allowing an object (computer science), object to be invoked or called as if it were an ordinary subroutine, function, usually with the same syntax (a function parameter that can also be a ...
s as written, and could correspond to
lambda expressions,
function pointer
A function pointer, also called a subroutine pointer or procedure pointer, is a pointer referencing executable code, rather than data. Dereferencing the function pointer yields the referenced function, which can be invoked and passed arguments ...
s and other types of
callable object
A callable object, in computer programming, is any object that can be called like a function.
In different languages
In C++
* pointer to function;
* pointer to member function;
* functor;
* lambda expression.
* std::function is a templa ...
s in the C++ programming language.
Improvements
When
is a vector of
, branch and bound algorithms can be combined with
interval analysis and
contractor techniques in order to provide guaranteed enclosures of the global minimum.
Applications
This approach is used for a number of
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
problems:
*
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
*
Nonlinear programming
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation ...
*
Travelling salesman problem
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
(TSP)
*
Quadratic assignment problem
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koo ...
(QAP)
*
Maximum satisfiability problem
In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth va ...
(MAX-SAT)
*
Nearest neighbor search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: ...
(by
Keinosuke Fukunaga)
*
Flow shop scheduling
*
Cutting stock problem
In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of Inventory, stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimizat ...
*
Computational phylogenetics
Computational phylogenetics, phylogeny inference, or phylogenetic inference focuses on computational and optimization algorithms, Heuristic (computer science), heuristics, and approaches involved in Phylogenetics, phylogenetic analyses. The goal i ...
*
Set inversion
In mathematics, set inversion is the problem of characterizing the preimage ''X'' of a set ''Y'' by a function ''f'', i.e., ''X'' = ''f''−1(''Y'' ) = . It can also be viewed as the problem of describing the solution set of the quantified c ...
*
Parameter estimation
Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value ...
*
0/1 knapsack problem
*
Set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.
Given a set of elements (henceforth referred to as the universe, specifying all possible elements under considerati ...
*
Feature selection
In machine learning, feature selection is the process of selecting a subset of relevant Feature (machine learning), features (variables, predictors) for use in model construction. Feature selection techniques are used for several reasons:
* sim ...
in
machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
*
Structured prediction
Structured prediction or structured output learning is an umbrella term for supervised machine learning techniques that involves predicting structured objects, rather than discrete or real values.
Similar to commonly used supervised learning t ...
in
computer vision
Computer vision tasks include methods for image sensor, acquiring, Image processing, processing, Image analysis, analyzing, and understanding digital images, and extraction of high-dimensional data from the real world in order to produce numerical ...
*
Arc routing problem
Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing p ...
, including Chinese Postman problem
*
Talent Scheduling, scenes shooting arrangement problem
Branch-and-bound may also be a base of various
heuristic
A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
s. 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
Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
.
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 solve this problem
Maximize
with these constraints
and
are integers.
The first step is to relax the integer constraint. We have two extreme points for the first equation that form a line:
and
. We can form the second line with the vector points
and
.

The third point is
. 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
, or
with a value of 276.667. 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
becomes the parameter for the branch and bound method. We branch to
and obtain 276 @
. We have reached an integer solution so we move to the other branch
. We obtain 275.75 @
. We have a decimal so we branch
to
and we find 274.571 @
. We try the other branch
and there are no feasible solutions. Therefore, the maximum is 276 with
and
.
See also
*
Backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
*
Branch-and-cut, a hybrid between branch-and-bound and the
cutting plane
In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...
methods that is used extensively for solving
integer linear programs.
*
Evolutionary algorithm
Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at least Approximation, approximately, for which no exact or satisfactory solution methods are k ...
*
Alpha–beta pruning
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the Minimax#Minimax algorithm with alternate moves, minimax algorithm in its game tree, search tree. It is an adversarial search algorith ...
References
External links
LiPS– Free easy-to-use GUI program intended for solving linear, integer and goal programming problems.
Cbc– (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.
{{DEFAULTSORT:Branch And Bound
Optimization algorithms and methods
Combinatorial optimization