Branch and bound
Encyclopedia
Branch and bound 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 in 1960 for discrete programming
.
, where 
ranges over some set 
of admissible or candidate solutions (the search space
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 structure
(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 of 
. 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 when the upper bound for set 
matches the lower bound. Either way, any element of 
will be a minimum of the function within 
.
problems, such as
Branch-and-bound may also be a base of various heuristic
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
. 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.
For this reason, branch-and-bound techniques are often used in game tree
search algorithm
s, most notably through the use of alpha-beta pruning
.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for finding optimal solutions of various optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problems, especially in discrete
Discrete optimization
Discrete 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 optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
. 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 discrete programming
Discrete optimization
Discrete 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...
.
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
Search 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 structureTree structure
A 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 of . 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 when the upper bound for set matches the lower bound. Either way, any element of will be a minimum of the function within .Applications
This approach is used for a number of NP-hardNP-hard
NP-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 problemKnapsack problemThe 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 count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
- Integer programmingInteger programmingAn 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, which is also known as mixed integer programming.Integer programming is NP-hard...
- Nonlinear programmingNonlinear programmingIn 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 problemQuadratic assignment problemThe 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 problemMaximum satisfiability problemIn computational complexity theory, the Maximum Satisfiability problem is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment...
(MAX-SAT) - Nearest neighbor searchNearest neighbor searchNearest 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 problemCutting stock problemThe 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 heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
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
Noise
In common use, the word noise means any unwanted sound. In both analog and digital electronics, noise is random unwanted perturbation to a wanted signal; it is called noise as a generalisation of the acoustic noise heard when listening to a weak radio transmission with significant electrical noise...
or is the result of statistical estimates
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
and so is not known precisely but rather only known to lie within a range of values with a specific probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
. An example of its application here is in biology
Biology
Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...
when performing cladistic analysis
Cladistics
Cladistics is a method of classifying species of organisms into groups called clades, which consist of an ancestor organism and all its descendants . For example, birds, dinosaurs, crocodiles, and all descendants of their most recent common ancestor form a clade...
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 tree
Game tree
In 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 complete tree is the same tree as that...
search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
s, most notably through the use of alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
.