Algorithms
Branch and Bound
Difficulty: Advanced
0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the...
Branch and Bound
0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound.
Branch and Bound introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach.
In Backtracking (Intro), you walked an implicit decision tree with choose, explore, unchoose. Greedy (Intro) taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other.
Next, Divide and Conquer (Advanced) turns to algebraic D&C tricks like Karatsuba and Strassen.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain how Branch and Bound extends backtracking with bounding functions to prune the search tree.
Distinguish between FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue) branching strategies and their trade-offs.
Implement Branch and Bound for the 0/1 Knapsack problem using the fractional knapsack upper bound.
Apply B&B to the Traveling Salesman Problem using a minimum spanning tree or nearest-neighbor lower bound.
Compare Branch and Bound with dynamic programming and backtracking for different problem types.
Why This Matters
01
Branch and Bound transforms exponential backtracking into practical solvers by eliminating provably suboptimal branches — it is the foundation of commercial optimization solvers (CPLEX, Gurobi).
02
The 0/1 Knapsack problem solved via B&B demonstrates how a tight upper bound (fractional relaxation) prunes the search tree dramatically, often solving instances exponentially faster than brute force.
03
Understanding the relationship between backtracking (explore all), greedy (explore one), and B&B (explore selectively) gives you a complete toolkit for optimization problems.
04
Branch and Bound appears in hard interview problems and competitive programming when dynamic programming is infeasible due to large state spaces.
Key Terms
6 terms you'll encounter in this lesson
Branch and Bound
An algorithmic paradigm for optimization that explores a state space tree, computing bounds at each node to prune subtrees that cannot contain the optimal solution.
Bounding Function
A function that computes an optimistic estimate of the best possible solution in a subtree. For maximization, an upper bound; for minimization, a lower bound. If the bound is worse than the best known solution, the subtree is pruned.
Pruning
Eliminating a subtree from exploration because its bound guarantees no solution in it can improve upon the current best. Effective pruning dramatically reduces the search space.
State Space Tree
A tree where each node represents a partial solution (a set of decisions made so far). The root is the empty solution, and leaves are complete solutions. B&B explores this tree selectively.
Live Node
A node in the state space tree that has been generated but whose children have not yet been fully explored. Live nodes are stored in a queue, stack, or priority queue depending on the search strategy.
Fractional Knapsack Bound
The upper bound for 0/1 Knapsack computed by allowing fractional items: take whole items greedily by value/weight ratio, and fractionally fill remaining capacity. This bound is tight and fast to compute.
Heads Up
Common misconceptions to watch out for
"Branch and Bound always runs faster than backtracking"
B&B has the same worst-case as backtracking (exponential), but it is typically much faster because the bounding function prunes large subtrees. The effectiveness depends entirely on the tightness of the bound — a loose bound provides little pruning.
"Branch and Bound finds the optimal solution at the first leaf"
B&B may visit many leaves before confirming optimality. The first complete solution found becomes the initial 'best so far', but subsequent branches might yield better solutions. The algorithm terminates only when all live nodes are pruned or explored.
"Branch and Bound is the same as greedy with backtracking"
Greedy makes irrevocable choices without guaranteeing optimality. B&B explores multiple paths and uses bounds to systematically prune, guaranteeing the optimal solution is found (it is exact, not heuristic).