Branch and Bound
Backtracking cuts a branch when it breaks a rule. Branch and bound also cuts branches that are perfectly legal but cannot win: at every node it computes an optimistic bound on the best answer reachable below, and if even that cannot beat the best complete answer already in hand, the subtree is never searched. On the 0/1 knapsack the bound is the value you would get by filling the remaining capacity with a fraction of the next item, which is always at least the true best because fractions can only help. Sorting the items by value per unit of weight makes that bound tight, so the very first leaf is usually close to optimal and most of the tree is cut on sight.
Pack a knapsack of capacity 5 from 4 items, each taken whole or not at all, for the most value. The items are sorted by value per unit of weight, best first: A (2 for 3), B (3 for 4), C (4 for 5), D (5 for 6). Search take-or-skip, item by item, but before entering any branch compute an optimistic bound, the value you would get if the rest of the capacity could be filled with a fraction of the next item. A branch whose bound cannot beat the best complete answer so far is cut without being searched.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
The bound here is 7 and the best complete answer is 0. Explore or prune?
Answer: Explore it, the bound beats the best. Prune only when the bound is at most the best. A bound above the best proves nothing, it only keeps hope alive; a bound at or below it proves the subtree cannot win.
The bound here is 7 and the best complete answer is 3. Explore or prune?
Answer: Explore it, the bound beats the best. Prune only when the bound is at most the best. A bound above the best proves nothing, it only keeps hope alive; a bound at or below it proves the subtree cannot win.
The bound here is 7 and the best complete answer is 7. Explore or prune?
Answer: Prune it, even the bound cannot beat the best. Prune only when the bound is at most the best. A bound above the best proves nothing, it only keeps hope alive; a bound at or below it proves the subtree cannot win.
The bound here is 6.8 and the best complete answer is 7. Explore or prune?
Answer: Prune it, even the bound cannot beat the best. Prune only when the bound is at most the best. A bound above the best proves nothing, it only keeps hope alive; a bound at or below it proves the subtree cannot win.
The bound here is 6.5 and the best complete answer is 7. Explore or prune?
Answer: Prune it, even the bound cannot beat the best. Prune only when the bound is at most the best. A bound above the best proves nothing, it only keeps hope alive; a bound at or below it proves the subtree cannot win.
How it runs, step by step
Pack a knapsack of capacity 5 from 4 items, each taken whole or not at all, for the most value. The items are sorted by value per unit of weight, best first: A (2 for 3), B (3 for 4), C (4 for 5), D (5 for 6). Search take-or-skip, item by item, but before entering any branch compute an optimistic bound, the value you would get if the rest of the capacity could be filled with a fraction of the next item. A branch whose bound cannot beat the best complete answer so far is cut without being searched.
Branch and bound knapsack, 4 items, capacity 5.
Deciding item A with nothing taken, weight 0 of 5, value 0. Fill the remaining 5 optimistically, fractions allowed: the bound is 7. The best complete answer is 0. The bound is higher, so the branch might still win: explore it, taking A first.
Bound 7 against best 0: explore.
Deciding item B with A taken, weight 2 of 5, value 3, already better than anything complete so far. Fill the remaining 3 optimistically, fractions allowed: the bound is 7. The best complete answer is 3. The bound is higher, so the branch might still win: explore it, taking B first.
Bound 7 against best 3: explore.
Deciding item C with A, B taken, weight 5 of 5, value 7, already better than anything complete so far. Fill the remaining 0 optimistically, fractions allowed: the bound is 7. The best complete answer is 7. Even the optimistic bound cannot beat that, so this whole subtree is cut: 4 leaves never visited.
Bound 7 against best 7: prune.
Deciding item C with A taken, weight 2 of 5, value 3. Fill the remaining 3 optimistically, fractions allowed: the bound is 6.8. The best complete answer is 7. Even the optimistic bound cannot beat that, so this whole subtree is cut: 4 leaves never visited.
Bound 6.8 against best 7: prune.
Deciding item B with nothing taken, weight 0 of 5, value 0. Fill the remaining 5 optimistically, fractions allowed: the bound is 6.5. The best complete answer is 7. Even the optimistic bound cannot beat that, so this whole subtree is cut: 8 leaves never visited.
Bound 6.5 against best 7: prune.
Best value 7 with A, B (weight 5 of 5). The search visited 5 nodes and cut 3 subtrees, out of 31 nodes in the full take-or-skip tree. Two things made the cutting safe: the bound never underestimates, because allowing a fraction of an item can only raise the value, and the incumbent is a real, complete answer. Branch and bound is backtracking plus that one comparison, and it is how exact solvers for hard problems get anywhere at all.
Best value 7 with A, B.
Write it yourself
Define bestValue(weights, values, capacity) and return the greatest value that fits in the capacity, taking each item at most once. It runs in your browser against this lesson's own 3 examples.
// The answer is the same as 0/1 knapsack; the lesson is the pruning. Any correct method is accepted here.function bestValue(weights, values, capacity) { return 0;}
Remember
- Prune when the optimistic bound is at most the best complete answer found so far.
- The bound must never underestimate: allowing fractions of an item can only raise it, so it is safe.
- Sort by value per weight first; a tight bound and a good first leaf is what makes the cutting bite.
Topics covered
Where this is used
Operations researchMixed-integer programming solvers
Gurobi, CPLEX, SCIP and the open-source CBC are branch and bound underneath. At each node the solver drops the whole-number requirement and solves the resulting linear program: a fractional answer is always at least as good as any integer one, so its value is exactly the optimistic bound, and branching means taking a variable that came back as 3.4 and splitting the node into x <= 3 and x >= 4. Cuts, heuristics and presolve all exist to tighten that bound so that more of the tree can be discarded without being searched.
LogisticsProving a route is the shortest one
Concorde has solved travelling salesman instances of tens of thousands of cities to proven optimality using branch and cut, which is branch and bound with extra inequalities added at each node to pull the bound closer to the truth. The roles flip for a minimisation problem: the bound is a lower bound on every tour below the node, and you cut once it already exceeds the shortest tour in hand. Finding a good route is easy, and proving no better one exists is entirely the bound's job.
GamesChess engines
Alpha-beta pruning, the search inside Stockfish and every classical engine, is branch and bound on a game tree, with alpha and beta as the two players' incumbents. A move is abandoned the moment the opponent has one reply making it worse than something already guaranteed on another line, because the remaining replies cannot undo that. Move ordering plays the part that sorting by value per weight plays here: search the likely-best move first and a perfectly ordered search reaches the same depth while visiting about the square root of the nodes a badly ordered one needs.
DatabasesSQL query planners
SQL Server's optimizer is built on Cascades, Goetz Graefe's rule-driven framework, and it searches top down carrying a cost limit: the cost of the cheapest complete plan found so far. A partial plan whose cost already passes that limit is dropped together with every plan that could be built on top of it, since adding operators only ever adds cost. That monotonicity is the assumption that makes a partial cost a legitimate bound, and it is what lets a planner skip most of a join space that grows factorially.
Why it works this way
Why prune on bound <= best and not bound < best
The bound is the most any answer in this subtree could ever reach, so when it only equals the incumbent the very best outcome down there is a tie, and a tie is worth nothing. Cutting on equality is what removes the large flat regions where many different packings score the same. The trap is that it also makes the search blind to alternative optima: if you need to count every best packing or return all of them, you have to weaken the test to strictly less and accept a far bigger tree.
Best-first visits fewer nodes, so why is this depth-first?
Always expanding the live node with the highest bound is known to visit the fewest nodes for a given bounding function, but it needs a priority queue of live nodes that can grow exponentially, while depth first keeps only the current root-to-node path, which is where the O(n) space comes from. There is a second cost. Best first spreads across shallow nodes, and a shallow node has decided only a few items, so the value it carries is small and the incumbent it feeds back climbs slowly. Depth first commits a take-or-skip choice for every item before it backtracks even once, so a full packing and a real incumbent exist after n steps and the pruning test has something to bite on. Real solvers dive depth first for that reason and use the bound ordering to choose where to dive next.
The bound is a Double and the answer is an Int, so floor it
Every item value here is a whole number, so the true best below a node is a whole number too and cannot exceed floor(bound). Pruning on floor(bound) <= best is strictly stronger than the raw comparison: with a bound of 30.7 and an incumbent of 30 the raw test searches the subtree and the floored test cuts it on sight. Rounding is dangerous in the other direction as well - if floating point ever lets the bound come out a hair below the truth you will cut the subtree holding the answer, and the run returns a slightly wrong number with nothing to signal it.
best holds the value, not the items
The function returns a number and nothing in it records which items produced that number. To recover the packing you carry the current take-or-skip decisions in an array and copy that array into a saved answer at the single place the incumbent improves. The copy is O(n), but it runs only on improvements, which are rare next to the number of nodes visited.
Read more
- Branch and boundWikipedia
- Knapsack problemWikipedia
- Alpha-beta pruningWikipedia
- Mixed-integer programmingGoogle OR-Tools · developers.google.com
- Concorde TSP solverUniversity of Waterloo · math.uwaterloo.ca
- Extensible Query Optimizers in PracticeMicrosoft Research · microsoft.com