|
Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It is basically an enumeration approach in a fashion that prunes the nonpromising search space. In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ...
Discrete optimization is a branch of optimization in applied mathematics and computer science. ...
Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...
The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming. 1960 (MCMLX) was a leap year starting on Friday (the link is to a full 1960 calendar). ...
In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...
General description The general idea may be described in terms of finding the minimal or maximal value of a function f(x) over a set of admissible values of the argument x called feasible region. In practice, minimization is applied when the function represents a cost, while maximization is applied when the function represents a value. 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 may be 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 constructed subregions. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ...
Another tool is bounding, which is a fast way of finding upper and lower bounds for the optimal solution within a feasible subregion.
For a given problem space an efficient division will divide the solution space into a small set containing high value (or low cost) solutions to be examined more closely and a larger set of their opposites (those to be ignored). While desirable, efficient divisions are often difficult to achieve in practice and so the creation of an effective algorithm is highly dependent upon the nature of the problem to be solved and the skill of the analyst creating the algorithm.
The core of the approach is a simple observation that (for a minimization task) if the lower bound for a subregion A from the search tree is greater than the upper bound for any other (previously examined) subregion B, then A may be safely discarded from the search. This step is called pruning. It is usually implemented by maintaining a global 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.
It may happen that the upper bound for a node matches its lower bound; that value is then the minimum of the function within the corresponding subregion. Sometimes there is a direct way of finding such a minimum. In both these cases it is said that the node is solved. Note that this node may still be pruned as the algorithm progresses.
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 minimum lower bound and the maximum 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 terminatated when some error criterion such as (max-min)/(min + max) falls below a specified value. In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ...
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. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ...
Distributed computing is a method of computer processing in which different parts of a program run simultaneously on two or more computers that are communicating with each other over a network. ...
The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...
Applications This approach is used for a number of NP-hard problems, such as In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...
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. Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under 15 kg? A multi dimensional problem could consider the density or dimensions of the boxes, the latter a typical packing problem. ...
In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...
The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...
The quadratic assignment problem (QAP) 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. ...
The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...
Look up Heuristic in Wiktionary, the free dictionary. ...
For the Irish mythological figure, see Naoise. ...
A graph of a Normal bell curve showing statistics used in educational assessment and comparing various grading methods. ...
Probability is the chance that something is likely to happen or be the case. ...
| 
Feeds |
Contact