Branch and Bound
Branch and bound is a systematic algorithm design paradigm for solving combinatorial optimization problems. It explores the solution space as a tree (branc...
The Branch and Bound Framework
Branch and bound is a systematic algorithm design paradigm for solving combinatorial optimization problems. It explores the solution space as a tree (branching), but uses bounds to prune subtrees that cannot lead to a better solution than the best one found so far (bounding). It combines the exhaustive coverage of backtracking with intelligent pruning based on optimization bounds.
Two key components: the branching strategy (how to split the current problem into sub-problems) and the bounding function (how to compute an upper or lower bound on the best solution reachable from the current partial solution). For maximization problems, compute an upper bound; if this upper bound is worse than the current best solution, prune the branch. For minimization, compute a lower bound; if it exceeds the current best, prune.
The quality of the bounding function is critical. A tight bound (close to the actual optimum of the sub-tree) prunes more aggressively and runs faster. A loose bound (far from the actual optimum) prunes little and degenerates toward brute force. Computing a tighter bound often requires more computation, so there is a trade-off between bound quality and computation cost per node.
A worked example: 0/1 knapsack with branch and bound. Branch on whether to include item 1 or not. For the subtree where item 1 is included, compute an upper bound by greedily filling the remaining capacity with fractions of remaining items (fractional knapsack bound). If this upper bound is less than the best integer solution found so far, prune the entire subtree.
Interview tip: Contrast branch and bound with backtracking: both explore a search tree with pruning, but backtracking checks feasibility (does this path satisfy constraints?) while branch and bound checks optimality (can this path possibly beat the current best solution?). This distinction is the fundamental difference.
Bounding Functions for Knapsack and TSP
Designing effective bounding functions is the art of branch and bound. For the 0/1 knapsack problem, the fractional knapsack upper bound is standard: given the items not yet decided, solve the fractional relaxation (allow fractions) greedily by value-per-weight ratio. The fractional optimum is always at least as good as the integer optimum, making it a valid upper bound. This bound is tight when all remaining items happen to fit exactly.
For the Travelling Salesman Problem (TSP), where you seek the minimum-cost tour visiting all cities exactly once, a common lower bound is the minimum spanning tree (MST) relaxation. Any tour must form a connected graph, and the cheapest connected spanning structure is the MST. So the MST weight plus the two cheapest edges incident to the start city is a lower bound on the tour cost. Held-Karp also provides a tighter bound using 1-tree relaxation.
The 0/1 knapsack branch and bound works as follows: sort items by value-per-weight ratio. Maintain a priority queue (max-heap) of live nodes ordered by their upper bound. Initially enqueue the root (no items decided). Extract the node with the highest upper bound. Branch: create two children (include item k, exclude item k). For each child, compute the new upper bound. If the upper bound exceeds the current best integer solution, enqueue the child; otherwise, prune. When a node represents a complete assignment (all items decided), update the best integer solution.
Best-first search (always explore the node with the best bound next) typically explores fewer nodes than depth-first. However, best-first requires a priority queue and may use more memory than depth-first, which uses a stack and explores deep quickly to establish a good incumbent solution early.
Interview tip: The choice of bounding function and node selection strategy (best-first vs. depth-first) are the two design decisions in branch and bound. Stating both and explaining the trade-off demonstrates that you understand the algorithm at a design level rather than just as a recipe.
Comparing Branch and Bound, Backtracking, and DP
Branch and bound, backtracking, and dynamic programming all handle combinatorial problems but are suited to different situations. Understanding their relationships and when to apply each is an important algorithmic thinking skill.
Backtracking explores the solution space tree exhaustively, pruning only when a partial solution violates hard constraints (feasibility). It finds all valid solutions or any one valid solution. It does not inherently optimize — it treats all valid solutions as equal. Typical use: N-queens, Sudoku, permutation enumeration.
Branch and bound extends backtracking with optimization bounds. It finds the single globally optimal solution among all valid solutions. At each node, it computes a bound on the best achievable value in the subtree and prunes if the bound cannot beat the current best. Typical use: 0/1 knapsack (when n is large), TSP, job scheduling.
Dynamic programming avoids redundant computation by memoizing overlapping sub-problems. It is exact and polynomial (pseudo-polynomial for knapsack). It requires optimal substructure and overlapping sub-problems. Typical use: knapsack with moderate W, LCS, shortest paths (Bellman-Ford). When n and W are small enough for O(n*W) to be feasible, DP is almost always faster than branch and bound for knapsack.
The practical decision: if the DP table fits in memory and runs in time, use DP. If n or W is huge making the DP table infeasible, use branch and bound with a good bounding function. If you need all solutions rather than the optimum, use backtracking.
Time complexity comparison for 0/1 knapsack: DP is O(n*W), branch and bound is O(2^n) in the worst case but often far better in practice. For n = 100 and W = 10^9, DP is infeasible (10^11 table entries) while branch and bound with a good bound can solve it quickly because most branches are pruned early.
Interview tip: When given a knapsack problem, immediately ask about the size of n and W. If W is small, say DP; if W is large but n is moderate, say branch and bound; if you need to verify all solutions, say backtracking. Asking about input constraints before choosing an algorithm demonstrates engineering judgment.