From 'is it possible?' to 'is it worth it?'
In the previous guide, backtracking walked the state-space tree depth-first and cut off any branch that violated a rule — an N-queens partial board with two queens attacking each other can never be completed, so we stopped exploring it. That is feasibility pruning: we kill a branch because it leads to no valid solution at all. But many problems are not asking "does a solution exist?" — they ask "which valid solution is best?" That is an optimization problem, and for those, a branch can be perfectly feasible yet still hopeless, because the best it could ever produce is worse than something we have already found.
Branch and bound is the name for that second kind of pruning. "Branch" is the same move as before: split the remaining choices into sub-cases and recurse. The new ingredient is the "bound": at every node we compute an optimistic estimate of the best score reachable from there. If even that rosy estimate cannot beat the best complete solution we have already banked — call it the incumbent — we prune the whole subtree without ever entering it. We are no longer asking "is this branch possible?" but "could this branch possibly be worth it?"
The bound must never lie in the optimistic direction
Everything rests on one rule, and it is worth stating with care. The bound at a node must be optimistic: for a maximization problem it must be an upper bound — a number no smaller than the true best score reachable below that node. (For minimization it flips: the bound must be a lower bound, no larger than the true best.) Why this exact direction? Because we prune a maximizing branch only when its upper bound is already no better than the incumbent. If the upper bound were ever too low — smaller than something actually reachable below — we might throw away the branch that held the real optimum. An honest, never-too-optimistic bound is what keeps the search correct: it can prune a subtree only when nothing inside it could have won.
Where does such a bound come from? The classic trick is to relax the problem: drop a constraint so the easier version can be solved fast, and its answer becomes a valid optimistic estimate. The relaxed answer is always at least as good as the real one — you removed a restriction, so you can only do better or equal — which is exactly the optimistic guarantee you need. The famous example is 0/1 knapsack: at a node where some items are decided, bound the rest by solving the fractional knapsack, where items may be cut into pieces. Greedily filling by value-per-weight gives the fractional optimum in one pass, and since cutting items can only help, that value is a true upper bound on what the integral 0/1 knapsack could still earn below this node.
A tiny trace: knapsack pruned by a bound
Make it concrete with three items and a knapsack of capacity 10. Item A: weight 4, value 40. Item B: weight 6, value 42. Item C: weight 5, value 25. Sort by value-per-weight: A is 10/unit, B is 7/unit, C is 5/unit. The state-space tree branches on each item in turn — left child takes it, right child skips it. We carry along the weight used, the value collected, and a bound = current value plus the fractional-knapsack value of the items not yet decided.
Dive left first (take A, then B): weight 4 + 6 = 10, value 40 + 42 = 82, and C no longer fits. That is a complete, feasible solution, so the incumbent becomes 82. Now back up and try the branch that takes A but skips B. Its bound is value-so-far 40 plus the best the remaining capacity 6 could fractionally hold from {C}: that is only 25, for a bound of 65. Since 65 is already no better than the incumbent 82, we prune that entire subtree — we never bother deciding C in it. The bound let us discard a feasible region without exploring a single leaf inside it, and the answer 82 is still provably optimal.
explore(node):
if node is a complete solution:
if value(node) > incumbent: incumbent = value(node)
return
if bound(node) <= incumbent: # optimistic estimate can't win
return # PRUNE the whole subtree
for child in branch(node):
explore(child)Order matters: which node to expand next
Plain backtracking is rigidly depth-first: it dives down one branch to the bottom before trying the next. Branch and bound is freer — because the only thing it truly needs is a strong incumbent early, so that the bound can prune hard. Two common strategies trade off differently. Depth-first branch and bound keeps the small memory footprint of recursion and races to a complete (if imperfect) solution quickly, giving you an incumbent to prune against right away. Best-first search instead keeps a priority queue of live nodes and always expands the one with the most promising bound — it tends to reach the true optimum sooner, but the queue can swell to hold an exponential number of nodes, costing a great deal of memory.
Either way, a second lever helps: explore the most promising child first. In the knapsack tree, trying the "take the item" branch before the "skip it" branch tends to build a high-value incumbent fast, which then prunes the weaker sibling branches harder. This is the same wisdom as good move-ordering in game search — finding a good answer early is not just satisfying, it actively shrinks the rest of the work. None of this changes which leaf is optimal; it only changes how quickly the bound starts paying off.
What it buys you, and what it does not
Be honest about the guarantee. Branch and bound is still, at heart, complete enumeration with the dead wood trimmed away. When it returns an answer it is provably optimal — the pruning only ever discarded branches that could not win. But in the worst case the bound prunes nothing and the search still visits an exponential number of nodes: branch and bound does not change a problem's worst-case complexity, it changes how often you hit that worst case. For 0/1 knapsack, the Traveling Salesman, and other hard optimization problems, no one knows a method that is polynomial in the worst case — these sit in the realm of NP-hardness, where a polynomial algorithm is not merely unknown but widely believed not to exist.
So why use it? Because on typical inputs a good bound prunes ferociously, and a search that is exponential in the worst case can finish in seconds in practice. It also has a property dynamic programming often lacks: it can report a good feasible answer plus a bound on how far that answer might be from optimal, so you can stop early with a quality guarantee — useful when you cannot afford to wait for proven optimality. Where the structure is right, exact DP methods like Held-Karp may win instead; branch and bound shines when the bound is tight, memory for a full DP table is too large, or you want an anytime answer.
Branch and bound is the last of our pruning ideas that still searches one tree top-down. The next guide takes a different angle entirely: when the search space is a product of two halves, you can sometimes solve each half separately and meet in the middle, trading exponential time for the square root of itself. Keep the core insight from here in your pocket — an honest optimistic bound lets you discard whole regions of a feasible search space without ever looking inside them, and that single idea is what turns brute force into something you can actually run.