Branch and bound #

Branch and bound is a generic algorithm paradigm, (c.f. divide and conquer) which involves building a tree over a (usually very large) decision space, and then pruning the tree (for the algorithm to be effective, the pruning needs to be agressive enough to reduce the exponential search space into something feasible). The pruning is done by removing solutions that are outside a range of constantly updating bounds, which are the values of a (hopefully easily computable) objective function.

Examples #

Some NP-hard problems where branch and bound is used in the solution:

• integer programming (branch and cut)
• travelling salesman problem
• set cover problem
• cutting stock problem