Branch and Bound Technique
- Branch and bound is a systematic method for solving optimization problems
- B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
- However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
- On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
- The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.