Branch and bound (BB) is a general
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
for finding optimal solutions of various
optimizationIn mathematics, optimization, or mathematical programming, refers to choosing the best element from some set of available alternatives.In the simplest case, this means solving problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or...
problems, especially in
discreteDiscrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
and
combinatorial optimizationCombinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution....
. 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.
Branch and bound (BB) is a general
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
for finding optimal solutions of various
optimizationIn mathematics, optimization, or mathematical programming, refers to choosing the best element from some set of available alternatives.In the simplest case, this means solving problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or...
problems, especially in
discreteDiscrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
and
combinatorial optimizationCombinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution....
. 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 in 1960 for
linear programmingIn mathematics, linear programming is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints...
.
General description
For definiteness, 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 spaceSearch space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...
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
tree structureA tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...
(the
search tree) whose
nodes are the subsets of .
Another tool is a procedure that computes upper and lower bounds for the minimum value of within a given subset . 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 A 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 also when the upper bound for set matches the lower bound. Either way, any element of will be a minimum of the function within .
Effective subdivision
The efficiency of the method depends strongly on the node-splitting procedure and on the upper and lower bound estimators. All other things being equal, it is best to choose a splitting method that provides non-overlapping subsets.
Ideally the procedure stops when all nodes of the search tree are either pruned or solved. At that point, all non-pruned subregions will have their upper and lower bounds equal to the global minimum of the function. In practice the procedure is often terminated after a given time; at that point, the minimum lower bound and the minimum upper bound, among all non-pruned sections, define a
rangeIn mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
of values that contains the global minimum. Alternatively, within an overriding time constraint, the algorithm may be terminated when some
error criterion, such as
(max - min)/(min + max), falls below a specified value.
The efficiency of the method depends critically on the effectiveness of the branching and bounding algorithms used; bad choices could lead to repeated branching, without any pruning, until the sub-regions become very small. In that case the method would be reduced to an exhaustive enumeration of the domain, which is often impractically large. There is no universal bounding algorithm that works for all problems, and there is little hope that one will ever be found; therefore the general paradigm needs to be implemented separately for each application, with branching and bounding algorithms that are specially designed for it.
Branch and bound methods may be classified according to the bounding methods and according to the ways of creating/inspecting the search tree nodes.
The branch-and-bound design strategy is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that the branch-and-bound method (1) does not limit us to any particular way of traversing the tree and (2) is used only for optimization problems.
This method naturally lends itself for
parallelParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
and
distributedDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
implementations, see, e.g., the traveling salesman problem article.
Applications
This approach is used for a number of
NP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems, such as
- Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible...
- Integer programming
An integer programming problem is any mathematical optimization or feasibility program in which some or all of the variables are restricted to be integral. In many settings the term integer program is used as short-hand for integer linear programming....
- Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
- Traveling salesman problem (TSP)
- Quadratic assignment problem
The quadratic assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems....
(QAP)
- Maximum satisfiability problem
Satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE....
(MAX-SAT)
- Nearest neighbor search
Nearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
(NNS)
- Cutting stock problem
The cutting stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers...
- False noise analysis (FNA)
Branch-and-bound may also be a base of various
heuristicHeuristic is an adjective for experience-based techniques that help in problem solving, learning and discovery. A heuristic method is particularly used to rapidly come to a solution that is hoped to be close to the best possible answer, or 'optimal solution'...
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
noisyIn common use, the word noise means unwanted sound or noise pollution. In both analog and digital electronics, noise or signal noise is an unwanted random addition to a wanted signal; it is called noise as a generalisation of the audible noise heard when listening to a weak radio transmission...
or is the result of
statistical estimatesStatistics is a branch of mathematics concerned with collecting and interpreting data. According to other definitions, it is a mathematical science pertaining to the collection, analysis, interpretation or explanation, and presentation of data. Statisticians improve the quality of data with the...
and so is not known precisely but rather only known to lie within a range of values with a specific
probabilityProbability is a way of expressing knowledge or belief that an event will occur or has occurred. In mathematics the concept has been given an exact meaning in probability theory, that is used extensively in such areas of study as mathematics, statistics, finance, gambling, science, and philosophy...
. An example of its application here is in
biologyBiology is the natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy...
when performing
cladistic analysisCladistics is a form of biological systematics which classifies living organisms on the basis of shared ancestry...
to evaluate evolutionary relationships between organisms, where the data sets are often impractically large without heuristics.
For this reason, branch-and-bound techniques are often used in
game treeIn combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position.The diagram shows the first two...
search algorithmIn computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer scientists that solve problems are kinds of search...
s, most notably through the use of
alpha-beta pruningAlpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games...
.
See also
- A* search algorithm
In computer science, A* is a best-first graph search algorithm that finds the least-cost path from a given initial node to one goal node ....
- Classes of algorithms by design paradigm