HOME

TheInfoList



OR:

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 \mathbf is a vector of \mathbb^n, 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 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 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