Overview
Branch and Bound explores the decision tree of a combinatorial problem, but prunes: at each node it computes an optimistic upper bound on what that branch could achieve, and abandons the branch if the bound cannot beat the best solution found so far. The 0/1 Knapsack is the classic demo.
Each item is a yes/no decision (branch), so the search tree has up to 2^n leaves; the bound (a fractional-knapsack relaxation) is what makes exhaustively exploring it avoidable in practice.
How Branch & Bound works
- Branch on the next item: create two children — one that takes it, one that skips it.
- At each node compute an optimistic upper bound on the best value reachable below it.
- Prune the node if its bound does not exceed the best complete solution found so far.
- Otherwise descend, updating the best solution whenever a feasible leaf improves it.
When to use it
- NP-hard optimization problems where exact answers matter: knapsack, travelling salesman, assignment.
- Instances where a tight bound prunes most of the tree, making the search tractable.
- Prefer dynamic programming or heuristics when weights are integers and bounded, or when approximate answers suffice.
Complexity analysis
In the worst case no branch is pruned and Branch and Bound degenerates to exhaustive search — O(2^n) for n binary decisions. In practice a good bound prunes large swaths of the tree, so it is dramatically faster than brute force on typical instances, though it offers no better asymptotic guarantee.
Frequently asked questions
How is Branch and Bound different from plain backtracking?
Backtracking prunes only branches that violate constraints (infeasible). Branch and Bound also prunes feasible branches whose optimistic bound cannot beat the incumbent best, so it discards far more of the tree in optimization problems.
What makes a good bound function?
It must be optimistic (never underestimate the branch's best value) yet tight (close to the true optimum). For knapsack, relaxing to the fractional version gives exactly such a bound.