Branch And Bound Algorithm
   HOME

TheInfoList



OR:

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 \mathbf is a vector of \mathbb^n, 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 Z=5x_1+6x_2 with these constraints x_1+x_2\leq 50 4x_1+7x_2\leq280 x_1, x_2\geq0 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: \begin x_1 \\ x_2 \end=\begin50 \\0\end and \begin0 \\50\end. We can form the second line with the vector points \begin0\\40\end and \begin 70\\0\end. The third point is \begin0\\0\end. 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 \begin70/3\\80/3\end, or \begin 23.333\\26.667\end 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 x_2 becomes the parameter for the branch and bound method. We branch to x_2\leq26 and obtain 276 @ \langle 24,26\rangle. We have reached an integer solution so we move to the other branch x_2\geq27. We obtain 275.75 @\langle 22.75, 27\rangle. We have a decimal so we branch x_1 to x_1\leq22 and we find 274.571 @\langle 22,27.4286\rangle. We try the other branch x_1\geq23 and there are no feasible solutions. Therefore, the maximum is 276 with x_1\longmapsto 24 and x_2\longmapsto 26.


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