Branch and bound (BB, B&B, or BnB) is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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, a g ...
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 combi ...
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
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 ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...
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
Ailsa Horton Land (; 14 June 1927 – 16 May 2021) was a Professor of Operational Research in the Department of Management at the London School of Economics and was the first woman professor of Operational Research in Britain. She is most well- ...
and
Alison Doig whilst carrying out research at the
London School of Economics
, mottoeng = To understand the causes of things
, established =
, type = Public research university
, endowment = £240.8 million (2021)
, budget = £391.1 millio ...
sponsored by
British Petroleum in 1960 for
discrete programming,
and has become the most commonly used tool for solving
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
optimization problems.
The name "branch and bound" first occurred in the work of Little ''et al.'' on the
traveling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or 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 cit ...
.
Branch and bound methods do not go deep like
Depth-first search; the first direction is lateral movement in the tree similar to
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 de ...
(BFS).
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 , called an objective function, among some set of admissible, or
candidate solution
In mathematical optimization, a feasible region, feasible set, search space, 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, potent ...
s. The set is called the search space, or
feasible region
In mathematical optimization, a feasible region, feasible set, search space, 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, potent ...
. 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 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''). Not all plum species or varieties can be dried into prunes. A prune is the firm-fleshed fruit (plum) of '' Prunus domestica'' varieties that have a high so ...
" 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, management, 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, a ...
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, including only woody plants with secondary growth, plants that are ...
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 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, as well as a problem-specific branching rule. As such, the generic algorithm presented here is a
higher-order function.
# Using a
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
, 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 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 __NOTOC__
Queue () may refer to:
* Queue area, or queue, a line or area where people wait for goods or services
Arts, entertainment, and media
*''ACM Queue'', a computer magazine
* ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
data structures 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 de ...
. A
stack (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 alon ...
algorithm. A
best-first branch and bound algorithm can be obtained by using a
priority queue 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 graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
and its descendant
A* search
A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, ...
. 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++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
-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 to be invoked or called as if it were an ordinary function, usually with the same syntax (a function parameter that can also be a function). Function objects are often c ...
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 that points to a function. As opposed to referencing a data value, a function pointer points to executable code within memory. Dereferencing the function poi ...
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 template ...
s in the C++ programming language.
Improvements
When
is a vector of
, branch and bound algorithms can be combined with
interval analysis
Interval arithmetic (also known as interval mathematics, interval analysis, or interval computation) is a mathematical technique used to Floating point error mitigation, put bounds on rounding errors and measurement errors in numerical 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, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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 or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or s ...
*
Travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or 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 cit ...
(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 Ko ...
(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 val ...
(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
Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varyi ...
*
Cutting stock problem
In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem ...
*
Computational phylogenetics
Computational phylogenetics is the application of computational algorithms, methods, and programs to phylogenetic
*
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 ...
*
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 valu ...
*
0/1 knapsack problem
*
Set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
*
Feature selection
In machine learning and statistics, feature selection, also known as variable selection, attribute selection or variable subset selection, is the process of selecting a subset of relevant features (variables, predictors) for use in model construc ...
in
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
*
Structured prediction
Structured prediction or structured (output) learning is an umbrella term for supervised machine learning techniques that involves predicting structured objects, rather than scalar discrete or real values.
Similar to commonly used supervised l ...
in
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
*
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, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
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 the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
.
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 d ...
*
Branch-and-cut, a hybrid between branch-and-bound and the
cutting plane methods that is used extensively for solving
integer linear programs
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
.
*
Alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to:
*The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
*Alpha Beta, a former chain of Californian supermarkets
*Alpha and beta anomers ...
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