Branch and Bound - Applications

Applications

This approach is used for a number of NP-hard problems, such as

• Knapsack problem
• Integer programming
• Nonlinear programming
• Traveling salesman problem (TSP)
• Quadratic assignment problem (QAP)
• Maximum satisfiability problem (MAX-SAT)
• Nearest neighbor search (NNS)
• Cutting stock problem
• False noise analysis (FNA)
• Computational phylogenetics

Branch-and-bound 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. An example of its application here is in biology when performing cladistic analysis to evaluate evolutionary relationships between organisms, where the data sets are often impractically large without heuristics.

For this reason, branch-and-bound techniques are often used in game tree search algorithms, most notably through the use of alpha-beta pruning.