Branch and bound
Branch and bound is a general method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It belongs to the class of implicit enumeration methods.
The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming.
General description
The general idea may be described in terms of finding the minimal value of a function f(x) over a set of admissible values of the argument x called 'feasible region'. Both f and x may be of arbitrary nature. A branch-and-bound procedure requires two tools.
The first one is a smart way of covering the feasible region by several smaller feasible subregions (ideally, splitting into subregions). This is called branching, since the procedure is repeated recursively to each of the subregions and all produced subregions naturally form a tree structure, called search tree or branch-and-bound-tree or something similar. Its nodes are the construced subregions.
Another tool is bounding, which is a fast way of finding upper and lower bounds for the optimal solution within a feasible subregion.
The core of the approach is a simple observation that if the upper bound for a subregion from the search tree is lower than the lower bound for another subregion, then the whole latter one may be safely discarded from the search. This step is called, as one might guess, pruning.
It may happen that for a node the upper bound matches the lower one. Clearly, this gives the local solution for the problem within the given subregion. Sometimes there can be another way of finding the local solution. In both these cases it is said that the node is solved.
The procedure stops when all nodes of the search tree are either pruned or solved. The optimal solution is the minimum of the local solutions for the non-pruned subregions.
This general approach has various flavors for various applications.
Of course, at the first glance it is not clear how it might work. Indeed, it is not immediately seen what can prevent from the worst case of branching without any pruning until each subregion contains only one feasible solution. Therefore the method is usually described in the context of a particular problem for which it is well suited.
Branch and bound methods may be classified according to the bounding methods and according to the ways of creating/inspecting the search tree nodes.
This method naturally lends itself for parallel and distributed implementations, see, e.g., the Travelling salesman problem article.
Applications
This approach is used for a number of NP-hard problems, such as
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.
References
A. H. Land and A. G. Doig, An Automatic Method for Solving Discrete Programming Problems Econometrica, Vol.28 (1960), pp. 497-520.
Related articles
Referenced By
List of combinatorics topics | List of mathematical topics | List of mathematical topics (A-C) | List of mathematics topics
|
