Discrete Mathsfor Engineers

8. Branch & Bound vs Backtracking vs Dynamic Programming

Branch & Bound is often introduced near Backtracking because both explore search trees.

It is also often compared with Dynamic Programming because all three methods are used to solve difficult combinatorial problems.

But their goals, assumptions, and mechanisms are different.

8.1 Branch & Bound vs Backtracking

Backtracking is mainly concerned with feasibility.

It explores a search tree and prunes branches when constraints are violated or when no valid completion is possible.

Branch & Bound goes further: it may also prune branches that are still feasible, but cannot lead to a solution better than the incumbent.

• Backtracking: prune because the branch is invalid
• Branch & Bound: prune because the branch is uncompetitive

8.2 Branch & Bound vs Dynamic Programming

Dynamic Programming is based on overlapping subproblems and optimal substructure.

Instead of exploring a search tree with pruning, it solves subproblems systematically and stores their results for reuse.

Branch & Bound, by contrast, explores a search tree of partial solutions and reduces work through pruning, not memoization.

• Dynamic Programming: avoid recomputation
• Branch & Bound: avoid exploring irrelevant regions

8.3 Where they overlap

These methods are not always completely separate.

For some optimization problems:

• Backtracking can be extended into Branch & Bound
• Dynamic Programming can solve the same problem more efficiently when its assumptions hold
• Branch & Bound may still be preferred if exact DP is too large or memory-intensive

So the right method depends not only on the problem, but also on the structure available to exploit.

8.4 When Backtracking is the right choice

Backtracking is a natural choice when:

• the goal is to find any valid solution,
• or enumerate all valid solutions,
• and pruning is mainly based on constraints.

Typical examples include:

• N-Queens
• Sudoku
• Permutation generation
• Constraint satisfaction problems

8.5 When Branch & Bound is the right choice

Branch & Bound is natural when:

• the problem is an optimization problem,
• the search space is combinatorial,
• and useful bounds can eliminate large regions of the tree.

It is especially valuable when exact optimality matters, but full exhaustive search is too expensive.

8.6 When Dynamic Programming is the right choice

Dynamic Programming is often the best choice when:

• the problem has overlapping subproblems,
• optimal substructure is present,
• and the state space is manageable enough to store.

In such cases, DP may outperform Branch & Bound because it transforms exponential search into structured computation over reusable states.

8.7 Comparative summary

• Backtracking: search + feasibility pruning
• Branch & Bound: search + optimality pruning
• Dynamic Programming: state reuse + recurrence structure

In short:

• Backtracking asks: can this branch still work?
• Branch & Bound asks: can this branch still win?
• Dynamic Programming asks: have we already solved this state?

8.8 Summary

• Backtracking is about validity
• Branch & Bound is about optimality
• Dynamic Programming is about reuse of overlapping work
• The three methods may solve related problems
• The right choice depends on the structure of the problem