Branch and Bound
Branch and bound explores the solution space by branching and prunes subtrees that cannot contain the optimum using bounds; it is used for discrete optimization.
Purpose
To solve combinatorial optimization problems exactly, accelerating search through pruning.
Mechanism
Maintain a global best bound. Branch: split the problem into subproblems. Bound: compute a lower/upper bound for each subproblem and prune if the bound is no better than the current best. Common in integer programming and TSP.
Use cases
- Integer programming
- TSP solving
- Combinatorial optimization