Branch and Bound

Branch and Bound is a systematic enumeration method for solving integer and combinatorial optimization problems. The algorithm works by: (1) Branching - partitioning the solution space into smaller subproblems by fixing variables; (2) Bounding - computing upper and lower bounds on the optimal solution for each subproblem using LP relaxations; (3) Pruning - eliminating subproblems that cannot contain better solutions than the current best. The process continues until all subproblems are either solved or pruned. Efficiency depends on branching strategy, bounding quality, and node selection rules.

» OR glossary