Editing Branch and bound (section)

== Applications ==
{{Prose|section|date=February 2023}}
This approach is used for a number of [[NP-hard]] problems:
* [[Integer programming]]
* [[Nonlinear programming]]
* [[Travelling salesman problem]] (TSP)<ref name="little">{{cite journal |last1=Little |first1=John D. C. |last2=Murty |first2=Katta G. |last3=Sweeney |first3=Dura W. |last4=Karel |first4=Caroline |title=An algorithm for the traveling salesman problem |journal=Operations Research |volume=11 |issue=6 |year=1963 |pages=972–989 |doi=10.1287/opre.11.6.972 |url=http://dspace.mit.edu/bitstream/handle/1721.1/46828/algorithmfortrav00litt.pdf|hdl=1721.1/46828 |hdl-access=free }}</ref><ref>{{cite book |author1-link=Richard W. Conway|author2-link=William L. Maxwell|first1=Richard Walter |last1=Conway |first2=William L. |last2=Maxwell |first3=Louis W. |last3=Miller |year=2003 |title=Theory of Scheduling |url=https://archive.org/details/theoryofscheduli0000conw |url-access=registration |publisher=Courier Dover Publications |pages=[https://archive.org/details/theoryofscheduli0000conw/page/56 56–61]|isbn=978-0-486-42817-8 }}</ref>
* [[Quadratic assignment problem]] (QAP)
* [[Maximum satisfiability problem]] (MAX-SAT)
* [[Nearest neighbor search]]<ref>{{cite journal |last1=Fukunaga |first1=Keinosuke |first2=Patrenahalli M. |last2=Narendra |title=A branch and bound algorithm for computing {{mvar|k}}-nearest neighbors |journal=IEEE Transactions on Computers |year=1975 |issue=7 |pages=750–753|doi=10.1109/t-c.1975.224297 |s2cid=5941649 }}</ref> (by [[Keinosuke Fukunaga]])
* [[Flow shop scheduling]]
* [[Cutting stock problem]]
* [[Computational phylogenetics]]
* [[Set inversion]]
* [[Set estimation|Parameter estimation]]
* [[0/1 knapsack problem]]
* [[Set cover problem]]
* [[Feature selection]] in [[machine learning]]<ref>{{cite journal |title=A branch and bound algorithm for feature subset selection |last1=Narendra |first1=Patrenahalli M. |last2=Fukunaga |first2=K. |journal=IEEE Transactions on Computers |volume=C-26 |issue=9 |year=1977 |pages=917–922 |doi=10.1109/TC.1977.1674939 |s2cid=26204315 |url=http://www.computer.org/csdl/trans/tc/1977/09/01674939.pdf}}</ref><ref>{{cite arXiv |last1=Hazimeh |first1=Hussein| last2=Mazumder |first2=Rahul |last3=Saab |first3=Ali |eprint=2004.06152 |title=Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization |date=2020|class=stat.CO }}</ref>
* [[Structured prediction]] in [[computer vision]]<ref>{{Cite journal | first1 = Sebastian | last1 = Nowozin | first2 = Christoph H. | last2 = Lampert | title = Structured Learning and Prediction in Computer Vision | journal = Foundations and Trends in Computer Graphics and Vision | volume = 6 | issue = 3–4 | year = 2011  | pages = 185–365  | doi = 10.1561/0600000033 | isbn = 978-1-60198-457-9| citeseerx = 10.1.1.636.2651 }}</ref>{{rp|267–276}}
* [[Arc routing problem]], including Chinese Postman problem
* [[Talent Scheduling]], scenes shooting arrangement problem

Branch-and-bound may also be a base of various [[heuristic]]s. 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 [[noise|''noisy'']] or is the result of [[statistics|statistical estimates]] and so is not known precisely but rather only known to lie within a range of values with a specific [[probability]].{{Citation needed|date=September 2015}}