The brute force of the previous lesson evaluated all 362,880 possible routes for Rutalia's courier just to keep one. It's a monumental waste: most of those routes were doomed from their very first legs, and we built them out in full anyway. This lesson teaches how to explore the solution space without enumerating it: backtracking, which abandons a branch as soon as it violates a constraint, and branch and bound, which additionally abandons it as soon as an optimistic bound proves it can no longer beat the best solution found. These are exact techniques — they preserve the optimality guarantee — and they are the real engine inside the integer programming solvers we mentioned in 02-01. At the end we will solve the same 10-point TSP from 02-02 and count, with numbers, how many nodes we saved.

1. Exploring without enumerating: the idea of pruning
2. The general backtracking template
3. Guided example: subsets that fit in the van
4. 0/1 knapsack by backtracking
5. Branch and bound: pruning by quality too
6. Best-first with a heap
7. B&B for Rutalia's TSP: counting prunes
8. The limits of exactness

Every combinatorial solution can be built through partial decisions: I load shipment E1 or I don't, then E2… or alternatively: the first stop is D, the second is A… Those decisions form a tree: the root is "nothing decided", each level adds one decision, and the leaves are complete solutions. Brute force visits every leaf. The key observation is that we can often condemn an entire subtree by looking only at its root:

• Feasibility pruning (backtracking): if the partial load already weighs 16 with capacity 15, no extension will be valid. There is no need to look at any of its leaves.
• Optimality pruning (branch and bound): if the best this branch could ever deliver — computed with an optimistic bound — is worse than the best complete solution I already have, the branch is useless even if it's feasible.

Cutting a node at depth k in a binary decision tree eliminates 2^(n−k) leaves at a stroke. Pruning early pays exponentially: all the engineering in this lesson is about earning the right to prune early.

Backtracking is a recursive template — recognize the structure from 01-03: base case, advance, and here also undo:

The four slots to fill in for each problem:

The undo is what gives the technique its name: when a subtree is exhausted, we backtrack to the previous state and try the next option. The call stack (01-03) maintains the path from the root to the current node; the memory used is only the tree's depth, Θ(n), even if the tree has millions of nodes.

A cultural note: the classic teaching example for backtracking is N-queens (place N queens on an N×N board so none attacks another), where the "this queen is already under attack" prune eliminates enormous branches. The template is identical to the one above; we'll stick to packages and vans, which is what Rutalia pays for.

Let's start with the simplest version: listing all valid subsets. Three shipments with weights [6, 5, 4] and a van of capacity 10. Each tree level decides on one shipment: the left branch is "load it", the right branch is "don't":

The {E1, E2} branch dies at depth 2: it weighs 11 > 10, so its two descendants (with and without E3) are never even generated. Of the 2³ = 8 possible leaves, backtracking visits 6. In a toy example the savings are anecdotal; with 30 shipments and tight loads, the same prune eliminates most of the 2³⁰ subsets.

Fine details: selection is a single list that gets modified and restored (append/pop) — much cheaper than copying the list on every call; and the prune lives in option A's if: the infeasible subtree is never generated.

To optimize (not just list), we add the accumulated value and remember the best complete solution seen. We use the instance from 02-02: capacity 15, weights [12, 7, 11, 8, 9], values [40, 24, 35, 26, 30], whose known optimum is 50 (E2+E4):

It works and it prunes the infeasible, but it has a blind spot: it explores branches that are feasible yet useless — lightweight combinations that will never reach €50. Feasibility pruning knows nothing about quality. For that we need the second idea.

Branch and bound (B&B) enriches the tree with two numbers:

• The incumbent (a lower bound when maximizing): the best complete solution found so far. It is a real achievement: anything worse is of no interest.
• Each node's optimistic bound (an upper bound when maximizing): a quick computation of the maximum value the best leaf in its subtree could ever reach. It must be genuinely optimistic — never an underestimate — or we will prune branches that contained the optimum, losing exactness.

Pruning rule: if optimistic_bound(node) ≤ incumbent, the entire subtree is discarded. The optimality guarantee is preserved because we only throw away branches provably incapable of improving.

Where do optimistic bounds come from? From relaxing the problem: solving an easier version whose optimum is always ≥ the real one. For the 0/1 knapsack, we know the perfect relaxation from 02-02: the fractional knapsack (allow splitting shipments). It's solved in Θ(n log n) with the density greedy, and its value always equals or exceeds the 0/1 value — it is the same problem with fewer constraints.

With this bound, the node "I've loaded nothing of value and I'm already at shipment 4" is pruned instantly: not even a fractional fill reaches the incumbent. That is B&B's general pattern: branch by generating children and bound to kill them early. And here a circle closes with 02-01: integer linear programming solvers do exactly this, using the LP's continuous relaxation as the optimistic bound — that's why we saw the continuous optimum (62.5) always beat the integer one (58).

One design decision remains: in what order do we explore the live nodes? Recursive backtracking goes depth-first (DFS, implicit in the call stack). But if we explore the nodes with the best optimistic bound first, we find good solutions sooner, the incumbent improves sooner, and the prunes arrive sooner. This is the best-first strategy, and the structure to implement it is one we planted in 01-04: a heap (heapq), which extracts the minimum in Θ(log n).

In practice they are combined (depth-first with a good child ordering, or best-first with a memory cap). We will use pure best-first to see the mechanism clearly.

On to the main course: the 10-point instance from 02-02 (reuse POINTS, NAMES, D, and route_length from that lesson). Now we minimize, so the roles flip: the incumbent is an upper bound (the best complete route known) and each node's bound is a lower, optimistic one: it must never overestimate the remaining kilometers.

Our bound, simple but honest: kilometers traveled + the cheapest edge leaving each still-pending point (including the current point, which still has to leave toward someone). No real route can spend less than that to leave each point, so it never overestimates. Finer bounds (like the minimum spanning tree over the pending points — a concept we'll formalize in 03-04) prune even more at the cost of more computation per node: it's B&B's eternal trade-off.

Reading the code, piece by piece:

• Each live node is a tuple (bound, km, route, visited). Since heapq orders by the first element, the heap always delivers the node with the smallest lower bound — best-first, exactly as advertised.
• The prune acts twice: when popping a node off the heap (its bound may have become obsolete if the incumbent improved while it waited) and before enqueuing children (we don't waste memory on the doomed).
• When a route is completed and improves the incumbent, all pending branches with a bound ≥ that value die in a chain reaction. That's why finding a good route early accelerates things so much: if you seed the incumbent with nearest neighbor's 43.1 km (exercise 3 of 02-02) instead of infinity, the prune bites from the very first node.

The numbers. In our run, the algorithm returns the exact optimum — 35.22 km, the same route as brute force — after expanding about 1,200 nodes and performing about 2,800 prunes (the exact figure varies slightly depending on how ties between equal bounds are broken). Let's put that in perspective:

Three orders of magnitude less work, the same mathematical guarantee. Note the middle row too: in the pure TSP, feasibility backtracking prunes nothing, because any partial permutation can be completed. The bound prune is the one doing all the work — each problem dictates which kind of prune makes sense.

Have we defeated the combinatorial explosion? No: we have delayed it. B&B is still exponential in the worst case; it only trims the factor with intelligence. With good bounds, the state of the art solves TSPs of hundreds or thousands of nodes, but any hard instance can blow up, and problems like jointly planning Rutalia's entire fleet (dozens of vans × hundreds of stops × time windows) remain out of exact reach under any reasonable compute budget. When that happens, the engineer changes the contract: give up the guarantee of optimality in exchange for very good solutions in predictable time. That is the territory of metaheuristics, and it is exactly where we are headed.

• "Optimistic" bounds that aren't. If your lower bound can overestimate (e.g. using the average edge instead of the minimum), you will prune branches that contained the optimum and the algorithm will return garbage dressed up as an exact result. Verify the property on paper: is it impossible for a real solution to cost less than my bound?
• Forgetting the undo. If you don't restore state after the recursive call (selection.pop()), subsequent branches inherit ghost decisions. Typical symptom: results that depend on the exploration order.
• Copying state at every node without need. route + [j] creates new lists — convenient and correct, but on large instances the copy cost dominates. The apply/undo alternative over a single structure is faster (and more delicate). Start clear, optimize later by measuring (01-02).
• Not seeding the incumbent. Starting with best = infinity wastes the early prunes. A cheap greedy (nearest neighbor, FFD…) gives an initial incumbent that activates pruning from minute zero. It's the greedy + B&B synergy: the greedy guarantees nothing, but it accelerates the one that does.
• An expensive bound that doesn't pay off. A bound that prunes 5% more but costs 10 times more per node makes the total worse. Measure nodes expanded × cost per node, not just nodes.
• Tip: always instrument your B&B with counters (nodes_expanded, prunes) as we did here. They are your dashboard: if the prunes don't grow when you improve the bound, the new bound isn't contributing.

1. Trace on paper. With capacity 10 and shipments (weight, value): P1 (6, 48), P2 (5, 35), P3 (5, 35) — the greedy counterexample from 02-02 — draw the backtracking tree (8 potential leaves) and mark: (a) which branches feasibility pruning cuts; (b) what the optimum is. Then compute the fractional bound of the root node and of the node "I discarded P1": what do they tell you?

2. Seeding the incumbent. Modify tsp_branch_and_bound to accept a parameter initial_km (starting upper bound) and run it with (a) infinity and (b) the 43.1 km from nearest neighbor. Compare nodes_expanded and prunes in both cases. Why does it improve?

3. A finer bound. The min_out bound ignores that the chosen edges must form a route. A cheap improvement: for each pending point, use the average of its two cheapest edges instead of a single one (each point in a cycle has one incoming and one outgoing edge). Argue why it is still a valid lower bound and implement it. Does it expand fewer nodes?

Exercise 1. (a) Feasibility pruning cuts: {P1,P2} (weight 11 > 10) before deciding on P3, and {P1,P3} (11). Surviving as leaves: {P1} (48), {P2,P3} (70), {P2} (35), {P3} (35), {} (0) — the optimum is {P2,P3} = 70. (b) Fractional bound of the root: densities 8, 7, 7 → P1 whole (48) + P2 (35, weight 11 > 10: only 4 of its 5 units fit) → 48 + 35·(4/5) = 76. Of the node "I discarded P1": P2 + P3 = exactly 10 of weight → bound 70, which is moreover achievable. Reading: the root promises ≤ 76 (optimistic, as it should be). Follow the "I loaded P1" branch: with 4 free units and P2 pending, its bound is 48 + 35·(4/5) = 76; after discarding P2, with P3 pending it is still 48 + 28 = 76; and after also discarding P3, it drops to 48. If we explore the "I discarded P1" branch first (best-first would, as the bounds tighten), the incumbent quickly reaches 70… and even so, the P1 branch survives as long as it promises 76. The pattern to retain: bounds tighten as you descend the tree, and the incumbent kills everything that promises a value less than or equal to it — here everything promising ≤ 70 eventually dies.

Exercise 2.

With initial_km = 43.1, nodes whose lower bound exceeds 43.1 die before any incumbent of the run's own exists: the prune works from the root. In our tests, the number of nodes expanded drops noticeably (and the number of early prunes rises); the effect is far more dramatic on larger instances, where without a seed the heap bloats with thousands of mediocre nodes before the first complete route. The combination "cheap heuristic for the incumbent + B&B for the certificate" is a standard professional pattern.

Exercise 3. Validity: in a cycle, each point has exactly one incoming edge and one outgoing edge. The cycle's total cost can be written as Σ (in + out)/2 over all points. Since for each point we use the average of its two cheapest edges, no real assignment of in/out can cost less: the bound never overestimates. Implementation: precompute two_min[i] = (d1 + d2) / 2 with the two smallest distances in row D[i], and add two_min[j] for each pending point (adjusting the points already partially connected). Being tighter (greater than or equal to the single-edge bound), it prunes strictly more: on our instance, the reduction in nodes expanded is noticeable with minimal extra cost per node. This game — investing in finer bounds to prune more — is, taken to the extreme with LP relaxations, what makes industrial ILP solvers competitive.

We have turned blind enumeration into a search with judgment: backtracking discards the infeasible as soon as it shows itself (recursive template with apply/explore/undo, linear memory), and branch and bound also discards the feasible-but-doomed using optimistic bounds — the fractional relaxation for the knapsack, the minimum edges for the TSP — with the best-first strategy served by the heap we learned in 01-04. The result on Rutalia's TSP speaks for itself: the same 35.22 km optimum that cost brute force 362,880 evaluations fell after expanding about 1,200 nodes, without yielding an inch on the guarantee. But we have also been honest about the limit: the combinatorial explosion is delayed, not defeated, and Rutalia's full fleet remains beyond the reach of any exact method. In the next lesson we will cross that frontier deliberately: genetic algorithms give up the certificate of optimality and, in exchange, find excellent solutions where B&B can't even get started. We'll find out what it feels like to work without a net — and how to do it with professional judgment.