Lesson 10 of 16

Prune with Branch and Bound

Finding a feasible answer does not prove it is best. Branch and bound estimates the best possible outcome of each remaining branch and discards branches that cannot improve the current answer.

Maximize value in a knapsack

Suppose a feasible solution already has value 12. Another branch has selected value 6, and all remaining items total 5 in value. Even ignoring weight limits, it can reach only 6 + 5 = 11, so it cannot beat 12.

Best known feasible value: 12

Branch A: current 6 + remaining at most 5 = bound 11 → stop
Branch B: current 8 + remaining at most 10 = bound 18 → explore

Assume nonnegative item values. Ignoring weight constraints gives an upper bound at least as large as the achievable value. It is safe but may be too loose to prune much.

Useful bounds are optimistic and close

For knapsack, allowing fractional items can give a tighter upper bound. Relaxing the original restrictions cannot decrease the best achievable value.

• Maximization: Prune when the upper bound cannot exceed the current best.
• Minimization: Prune when the lower cost bound cannot improve on the current best.
• Requirement: The current best must come from a genuinely feasible solution.

If you need every optimal solution, preserve tied branches. Finding one optimum and enumerating all optimal answers require different stopping rules.

Compare with backtracking

Backtracking commonly rejects constraint violations. Branch and bound may reject a branch that still contains feasible answers because none can be better. Both prune, and both may still inspect many candidates in the worst case. Optimality requires safe bounds and complete exploration of necessary branches.

Check your understanding

A branch can really gain up to 10 more, but you mistakenly estimate only 3. Why is this dangerous?