Branch and bound


Branch and bound

Branch and bound (BB) 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 linear programming.

General description

For definiteness, we assume that the goal is to find the minimum value of a function f(x) (e.g., the cost of manufacturing a certain product), where x ranges over some set S of "admissible" or "candidate solutions" (the "search space" or "feasible region").

A branch-and-bound procedure requires two tools. The first one is a "splitting" procedure that, given a set S of candidates, returns two or more smaller sets S_1, S_2, ldots whose union covers S. Note that the minimum of f(x) over S is min{v_1, v_2, ldots}, where each v_i is the minimum of f(x) within S_i. This step is called branching, since its recursive application defines a tree structure (the "search tree") whose "nodes" are the subsets of S.

Another tool is a procedure that computes upper and lower bounds for the minimum value of f(x) within a given subset S. This step is called bounding.

The key idea of the BB algorithm is: if the "lower" bound for some tree node (set of candidates) A is greater than the "upper" bound for some other node B, then A may be safely discarded from the search. This step is called pruning, and is usually implemented by maintaining a shared variable m that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than m can be discarded.

The recursion stops when the current candidate set S is reduced to a single element; or also when the upper bound for set S matches the lower bound. Either way, any element of S will be a minimum of the function within S.

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 maximum lower bound and the minimum upper bound, among all non-pruned sections, define a range 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 parallel and distributed implementations, see, e.g., the traveling salesman problem article.

Applications

This approach is used for a number of NP-hard problems, such as

* Knapsack problem
* Integer programming
* Nonlinear programming
* Traveling salesman problem (TSP)
* Quadratic assignment problem (QAP)
* Maximum satisfiability problem (MAX-SAT)
* Nearest neighbor search (NNS)
* False noise analysis (FNA)

It may also be a base of various heuristics. 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 algorithms, most notably through the use of alpha-beta pruning.

See also

* A* search algorithm
* Classes of algorithms by design paradigm

External links

* [http://plagiata.net.ru/?p=100 Branch and bound on Delphi]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Branch-and-Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen …   Deutsch Wikipedia

  • Branch and bound — Séparation et évaluation Un algorithme par séparation et évaluation, également appelé selon le terme anglo saxon branch and bound, est une méthode générique de résolution de problèmes d optimisation, et plus particulièrement d optimisation… …   Wikipédia en Français

  • Branch-and-Bound-Verfahren — Branch and Bound Verfahren,   Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-bound-Verfahren —   [ brɑːntʃənd baʊnd ; englisch], Operationsresearch: Entscheidungsbaumverfahren …   Universal-Lexikon

  • Branch-and-Bound-Verfahren — 1. Begriff: Verfahren des ⇡ Operations Research, bei dem ein zu lösendes kombinatorisches Optimierungsproblem (endliche Anzahl unabhängiger Variablen mit diskretem Wertevorrat) keiner effektiven analytischen Behandlung zugänglich ist oder… …   Lexikon der Economics

  • Branch and Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch-and-Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… …   Deutsch Wikipedia

  • Branch and cut — (sometimes written as branch and cut ) is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values. The method is a hybrid of… …   Wikipedia