Editing Branch and bound (section)

{{Short description|Optimization by eliminating non optimal solutions to sub-problems}}
'''Branch and bound''' ('''BB''', '''B&B''', or '''BnB''')  is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. 

It is an [[algorithm]] [[algorithmic paradigm| design paradigm]] for [[discrete optimization|discrete]] and [[combinatorial optimization]] 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]]: the set of candidate solutions is thought of as forming a [[Tree (graph theory)|rooted tree]] 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]] and [[Alison Harcourt|Alison Doig]] whilst carrying out research at the [[London School of Economics]] sponsored by [[BP|British Petroleum]] in 1960 for [[discrete optimization|discrete programming]],<ref name=land_doig>{{cite journal |author = A. H. Land and A. G. Doig | year = 1960 | title = An automatic method of solving discrete programming problems | journal = Econometrica | volume = 28 | issue = 3 | pages = 497–520 | doi=10.2307/1910129| jstor = 1910129 }}</ref><ref>{{Cite web|url=http://www.lse.ac.uk/newsletters/pressAndInformation/staffNews/2010/20100218.htm|title=Staff News|website=www.lse.ac.uk|access-date=2018-10-08|archive-date=2021-02-24|archive-url=https://web.archive.org/web/20210224173541/https://www.lse.ac.uk/newsletters/pressAndInformation/staffNews/2010/20100218.htm|url-status=dead}}</ref> and has become the most commonly used tool for solving [[NP-hard]] optimization problems.<ref name="clausen99"/> The name "branch and bound" first occurred in the work of Little ''et al.'' on the [[traveling salesman problem]].<ref name="little"/><ref>{{cite report |last1=Balas |first1=Egon |first2=Paolo |last2=Toth |year=1983 |title=Branch and bound methods for the traveling salesman problem |issue=Management Science Research Report MSRR-488 |publisher=[[Carnegie Mellon University]] Graduate School of Industrial Administration |url=http://apps.dtic.mil/dtic/tr/fulltext/u2/a126957.pdf |url-status=live |archive-url=https://web.archive.org/web/20121020235044/http://www.dtic.mil/dtic/tr/fulltext/u2/a126957.pdf |archive-date=October 20, 2012}}</ref>