Travelling Salesman (Branch & Bound)

Grow partial tours, compute a lower bound on the cheapest possible completion, and prune any partial tour that can't beat the best full tour found.

9 min read Watch it move Build it

The travelling salesman problem (TSP) asks for the shortest tour that visits every city exactly once and returns to the start. Trying every order is (n − 1)! — astronomically large. Branch and bound tames it by growing partial tours city by city while keeping a lower bound on how cheaply each partial tour could possibly finish. The instant that optimistic estimate is no better than the best complete tour found, the branch is pruned.

Branch: extend the partial tour

Fix a start city (say A) to avoid counting the same cyclic tour n times. Each branch adds one more unvisited city to the current path, growing the search tree one level. A leaf is a full tour; its cost is the sum of edges plus the return edge to A.

Bound: the cheapest possible finish

Since TSP is a *minimisation*, the bound is a lower bound — a cost the branch can never go below. A classic estimate: for every city, add its two cheapest incident edges and divide the total by two. Every city in any tour uses exactly two edges (one in, one out), so this can never overestimate the true tour cost. As cities get committed to the path, the bound tightens.

Prune when the floor is too high

If a partial tour's lower bound — the least it could *possibly* cost to complete — is already ≥ the best full tour you've found, then no completion of it can win. Cut the branch without extending it further.

Worked example

Four cities with symmetric distances: AB 10, AC 15, AD 20, BC 35, BD 25, CD 30. Compute the root lower bound from each city's two cheapest edges:

A: cheapest two = 10(B), 15(C) -> 25
B: cheapest two = 10(A), 25(D) -> 35
C: cheapest two = 15(A), 30(D) -> 45
D: cheapest two = 20(A), 25(B) -> 45
sum = 150,  lower bound = 150 / 2 = 75

optimal tour:  A - B - D - C - A
               10 + 25 + 30 + 15 = 80

The optimal tour costs 80, and the root lower bound of 75 sits just below it — exactly what a valid lower bound should do. During the search, any partial tour whose bound climbs to 80 or more (once an 80-cost tour is known) is pruned immediately, so most of the 3! = 6 orderings here are never fully expanded.

Still exponential in the worst case

Branch and bound is not a polynomial algorithm — TSP is NP-hard, and on adversarial inputs the bounds prune little and the tree blows up. The bound is a heuristic that usually helps enormously, not a guarantee of speed.

OperationTimeSpace

Worst case · weak pruning — explore most toursO(n!)O(n)

Bound per node · scan edges for cheapest per cityO(n²)O(n)

In practice · good bounds cut the search hard≪ n!O(n)

Check yourself

Why is the TSP branch-and-bound estimate a *lower* bound rather than an upper bound?