Branch and Bound Method

The branch and bound method ( eng. Branch and bound ) is a general algorithmic method for finding optimal solutions to various optimization problems, especially discrete and combinatorial optimization . The method is a development of the method of complete enumeration , in contrast to the latter, with the screening of subsets of admissible solutions that are obviously not containing optimal solutions.

The branch and bound method was first proposed in 1960 by Ailsa Land and Alison Doig ^[1] for solving integer programming problems.

The general idea of the method can be described by the example of finding the minimum of a function. $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ on the set of acceptable values of the variable $x$ ${\ displaystyle x}$ $x$ . Function $f$ ${\ displaystyle f}$ $f$ and variable $x$ ${\ displaystyle x}$ $x$ may be of arbitrary nature. The branch and bound method requires two procedures: branching and finding estimates (boundaries).

The branching procedure consists in splitting the set of permissible values of a variable. $x$ ${\ displaystyle x}$ $x$ on subregions (subsets) of smaller sizes. The procedure can be recursively applied to subdomains. The resulting subregions form a tree , called the search tree or the tree of branches and borders . The nodes of this tree are constructed subregions (subsets of the set of values of the variable $x$ ${\ displaystyle x}$ $x$ ).

The procedure for finding estimates is to search for upper and lower bounds for solving the problem on a subdomain of the permissible values of the variable $x$ ${\ displaystyle x}$ $x$ .

The basis of the branch and bound method is the following idea: if the lower bound of the function’s values on a subdomain $A$ ${\ displaystyle A}$ $A$ the search tree is larger than the upper bound on any previously viewed subdomain $B$ ${\ displaystyle B}$ $B$ then $A$ ${\ displaystyle A}$ $A$ can be excluded from further consideration ( dropout rule ). Usually, the minimum of the resulting upper estimates is written to the global variable. $m$ ${\ displaystyle m}$ $m$ ; any node in the search tree whose lower bound is greater than the value $m$ ${\ displaystyle m}$ $m$ may be excluded from further consideration.

If the lower bound for the tree node coincides with the upper bound, then this value is the minimum of the function and is reached on the corresponding subdomain.

The method is used to solve some NP-complete problems, including the traveling salesman problem and the knapsack problem .

Notes

↑ AH Land and AG Doig . An automatic method of solving discrete programming problems, pp. 497-520.

[land_doig-1] AH Land and AG Doig . An automatic method of solving discrete programming problems, pp. 497-520.

Branch and Bound Method

See also

Notes

More articles: