Branch and bound

Read first

• Post 2: Why is the TSP hard? There are (n − 1)!/2 tours, the TSP is NP-hard, and a heuristic’s tour carries no proof of its quality. We measure tours by their gap to the optimum.
• Primer A: graphs A spanning tree connects all vertices with no cycle, and a minimum spanning tree (MST) is the cheapest one. The degree of a vertex is the number of edges touching it. In a tour, every vertex has degree 2.

The question this post answers: how do we prove a tour is optimal without looking at every tour, and without Held-Karp’s giant table?

Intuition

Branch and bound runs on two numbers. The upper bound (UB) is the cost of the best tour found so far. Any tour gives you one. The lower bound (LB) is a number that is guaranteed to be at most the cost of every tour in some group of tours. If a group’s lower bound is already at least the upper bound, nothing in that group can beat what you have, and you throw the whole group away without looking inside. That is pruning. Branching splits a group into smaller groups, so their bounds get tighter.

I will use the same six stops as in the Held-Karp post: coordinates in kilometres, distances in units of 100 m, rounded. The optimum is 247.

The upper bound. Nearest neighbour from A gives A-G-B-C-D-H-A: 36 + 45 + 36 + 41 + 28 + 106 = 292. So UB = 292.

The lower bound: a 1-tree. Take a tour and delete A. What remains is a path through B, C, D, G and H, and a path is a spanning tree of those five stops. So the tour costs at least the minimum spanning tree on {B, C, D, G, H}, plus the two edges at A. The two edges at A cost at least as much as A’s two cheapest edges. That structure, an MST on everything except A plus A’s two cheapest edges, is called a 1-tree, and its cost is a lower bound on every tour.

Computing it by hand with Kruskal’s rule (take the cheapest edge that does not close a cycle):

1. D–H 28, B–C 36, C–D 41 join B, C, D and H.
2. G joins through B–G 45. D–G also costs 45; I break the tie alphabetically.
3. MST on {B, C, D, G, H} = 28 + 36 + 41 + 45 = 150.
4. A’s two cheapest edges: A–G 36 and A–B 41, total 77.
5. LB = 150 + 77 = 227.

So the optimum lies between 227 and 292. Step through the diagram below to see the starting tour, the root 1-tree, and the two tours the search finds later; the 1-tree is not a tour because B has three edges and H has one. As in earlier posts, the drawn lengths are unrounded kilometres.

Branching on edges. B has degree 3, so one of its 1-tree edges must go. I pick B’s most expensive 1-tree edge, B–G, and split all tours into two groups: tours without B–G and tours with B–G. In each group I recompute the 1-tree with that rule enforced. A forbidden edge is never used; a forced edge is always used. Two more rules keep the bookkeeping honest. Once a stop has two forced edges, all its other edges are forbidden. If a stop has only two allowed edges left, both are forced.

Here is the whole search, starting from UB = 292. I explore depth-first, and the “without” child first. At each node I branch on the most expensive free 1-tree edge at the stop with the highest degree. In the diagram below, each box is a node with its lower bound, and each arrow is labelled with the edge rule it adds.

flowchart TD
  N1["1 root: LB 227"] -->|"B–G out"| N2["2: LB 227"]
  N1 -->|"B–G in"| N13["13: LB 227"]
  N2 -->|"D–G out"| N3["3: LB 236"]
  N2 -->|"D–G in"| N8["8: LB 227"]
  N3 -->|"C–G out"| N4["4: tour 254, new UB"]
  N3 -->|"C–G in"| N5["5: LB 236"]
  N5 -->|"C–D out"| N6["6: LB 256, pruned"]
  N5 -->|"C–D in"| N7["7: LB 263, pruned"]
  N8 -->|"C–D out"| N9["9: LB 240"]
  N8 -->|"C–D in"| N12["12: LB 260, pruned"]
  N9 -->|"C–G out"| N10["10: tour 247, new UB"]
  N9 -->|"C–G in"| N11["11: LB 275, pruned"]
  N13 -->|"A–B out"| N14["14: LB 257, pruned"]
  N13 -->|"A–B in"| N15["15: LB 236"]
  N15 -->|"D–G out"| N16["16: LB 245"]
  N15 -->|"D–G in"| N19["19: LB 271, pruned"]
  N16 -->|"C–G out"| N17["17: LB 263, pruned"]
  N16 -->|"C–G in"| N18["18: LB 280, pruned"]

The tree above is the full search: 19 nodes, each one a 1-tree computation. Nodes are numbered in the order they were explored. Nodes 6 and 7 were pruned against the upper bound of 254; every later pruned node was pruned against 247. Three moments are worth tracing by hand.

• Node 3 forbids B–G and D–G. G’s cheapest remaining link into the tree is C–G 54, so the MST becomes 28 + 36 + 41 + 54 = 159, and LB = 159 + 77 = 236.
• Node 4 also forbids C–G, so G has to hang off H through G–H 72. The 1-tree is A–B, B–C, C–D, D–H, H–G, G–A. Every stop has degree 2, so this 1-tree is a tour, cost 254. The upper bound drops from 292 to 254.
• Node 10 finds a 1-tree that is the tour A-B-C-H-D-G-A, cost 247. After that, every remaining node has LB ≥ 247 and is pruned on sight.

When no open nodes remain, the incumbent 247 is proven optimal. Every tour belonged to some leaf of this tree, and every leaf either held a tour no better than 247 or had a lower bound of at least 247.

The formal idea

Let 𝒯 be the set of all tours and c(T) the cost of tour T. A node of the search tree is a subset of 𝒯 described by two edge sets: I, the edges every tour in the node must use, and X, the edges no tour in the node may use.

Upper bound. UB = c(T*) for the best tour T* found so far. Initially it comes from a heuristic, or UB = ∞.

Lower bound. A function LB(node) with LB(node) ≤ c(T) for every tour T in the node. Usually you get one by solving a relaxation: an easier problem whose feasible set contains every tour.

Pruning rule. If LB(node) ≥ UB, discard the node. If the relaxation’s solution happens to be a tour, update UB and stop exploring that node.

Branching. Pick an edge e that is free (in neither I nor X). Create two children, one with e added to X and one with e added to I. Every tour in the parent is in exactly one child, so nothing is lost and nothing is counted twice. Branching on edges this way goes back to Little, Murty, Sweeney and Karel (1963), the paper that named the method “branch and bound.”

The diagram below is the whole method as a loop. Everything else in this post is a choice inside one of its boxes: which bound, which edge, which open node next.

flowchart TD
  P["Pick an open node"] --> B["Compute its lower bound"]
  B --> Q{"LB ≥ UB?"}
  Q -- yes --> X["Prune the node"]
  Q -- no --> T{"Relaxation is a tour?"}
  T -- yes --> U["Update UB"]
  T -- no --> S["Branch: edge out, edge in"]
  S --> E{"Open nodes left?"}
  X --> E
  U --> E
  E -- yes --> P
  E -- no --> O["Best tour is optimal"]

Three lower bounds matter for the TSP. The table below shows how close each gets on berlin52, whose optimum is 7,542. The numbers come from my own code, described below the table.

Assignment bound. Give every city exactly one successor and one predecessor, at minimum total cost, ignoring whether the result is one cycle. Every tour is such an assignment, so the minimum assignment is a lower bound. On our six stops it is 200: three two-city loops, A⇄G, B⇄C and D⇄H. Little et al. built their bounds from assignment-style matrix reductions. The assignment bound is strongest on asymmetric instances. On symmetric ones, two-city loops like A⇄G are cheap and drag it down.

1-tree bound. Choose a special city r. A 1-tree is a spanning tree on the other n − 1 cities plus two edges at r. Every tour is a 1-tree in which every city has degree 2, so the cheapest 1-tree is a lower bound. Held and Karp (1970) introduced it. My code computed it with an O(n²) MST: on berlin52 it gives 6,172 with city 1 as r, and 6,553 if you try all 52 choices of r and keep the best.

Lagrangian relaxation. This is the Held-Karp bound, from the same Held and Karp papers (1970, 1971). Give every city i a penalty πᵢ and replace each cost with d’(i, j) = d(i, j) + πᵢ + πⱼ. A tour uses exactly two edges at every city, so every tour’s cost goes up by exactly 2 Σπᵢ. The ranking of tours does not change, but the cheapest 1-tree does. So

L(π) = (cost of the cheapest 1-tree under d')  −  2 · Σᵢ πᵢ   ≤   c(T)   for every tour T

holds for any π, and we want the π that makes L(π) largest. The intuition is simple: raise πᵢ at cities with degree above 2, which makes the 1-tree avoid them, and lower it at leaves, which attracts edges to them. On our six stops, one adjustment does it. Add 20 at B (degree 3) and subtract 20 at H (degree 1). Σπ = 0, so the bound is just the new 1-tree cost. Edges at B now cost 20 more and edges at H 20 less. Recompute the 1-tree: it costs 247, and one minimum 1-tree is the tour A-B-C-H-D-G-A itself. The cheapest 1-tree is now a tour, so 247 is both a lower bound and the cost of a real tour: it is proven optimal at the root, with no branching at all.

For berlin52 the best possible value of this bound, the Held-Karp bound, is exactly 7,542. It equals the linear-programming bound from the next post’s formulation, which I computed directly. That matches TSPLIB’s optimum, so at the root this bound alone is enough to prove 7,542 optimal. In practice you approach the bound with a subgradient method, which moves each πᵢ in proportion to (degree − 2); how close you get in a fixed number of steps depends on how the step size is tuned. Because tour lengths are integers, any bound above 7,541 already proves it.

Search order. Which open node do you expand next?

• Depth-first dives to a leaf quickly, so it finds tours, and therefore upper bounds, early, and it needs memory only for the current path. My trace above is depth-first.
• Best-first always expands the open node with the smallest LB. It never expands a node whose LB is above the optimum, but it can hold a huge frontier in memory.

The branching choice matters as much as the order. On the six stops, I varied two choices: branch on the most expensive or the cheapest free 1-tree edge at the busiest stop, and try the “out” or the “in” child first.

Same bound, same instance, same optimum, and a five- to sixfold difference in work. (The exact counts for the “cheapest” rows depend on how ties between equal-cost edges are broken.) There are only 60 tours here, so the bad choices explore more nodes than brute force has tours.

Common misconceptions

“Branch and bound avoids exponential time.” Its worst case is still exponential. It is fast when the bounds are tight and the branching is sensible, and slow otherwise. Note the 115 nodes in the table, for a problem with 60 tours.

“A good heuristic tour is all you need to prune.” Pruning compares a lower bound with the upper bound. With a perfect upper bound of 247 from the start, the plain 1-tree bound of 227 at the root still prunes nothing there. Both bounds have to be good.

“The minimum spanning tree is a lower bound, so it’s good enough.” It is valid, but on berlin52 the plain 1-tree sits 18.2% below the optimum. A node is pruned only when its bound climbs above the best tour, and an 18% shortfall means it almost never does near the top of the tree.

“Branch and bound is a 1960s method that nobody uses.” It is the outer loop of modern exact TSP and VRP codes. Concorde, for example, combines branching with much stronger linear-programming bounds, and the 81,998-stop Korea tour in 2025 needed a branch-and-bound tree of 2,121 nodes.

Try it in Python

Branch and bound needs two numbers, and plain Python gets both for berlin52. Any tour is an upper bound, so the nearest-neighbour tour from Post 2 will do. The 1-tree from this post is a lower bound. Together they give a proven worst-case gap, even without running the full search.

import math

body = open("berlin52.tsp").read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
xy = [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]
n = len(xy)
d = [[int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in xy] for p in xy]  # EUC_2D

def one_tree_bound(d, special=0):
    """Minimum spanning tree on all cities except `special` (Prim),
    plus the two cheapest edges at `special`."""
    rest = [v for v in range(len(d)) if v != special]
    best = {v: d[rest[0]][v] for v in rest[1:]}
    total = 0
    while best:
        v = min(best, key=best.get)
        total += best.pop(v)
        for u in best:
            best[u] = min(best[u], d[v][u])
    return total + sum(sorted(d[special][v] for v in rest)[:2])

def nearest_neighbour_cost(d, start=0):
    tour, left = [start], set(range(len(d))) - {start}
    while left:
        nxt = min(left, key=lambda c: (d[tour[-1]][c], c))
        tour.append(nxt)
        left.remove(nxt)
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

ub = nearest_neighbour_cost(d)   # upper bound: any tour will do
lb = one_tree_bound(d)           # lower bound: no tour can be cheaper
print(f"upper bound (nearest neighbour): {ub}")
print(f"lower bound (1-tree):            {lb}")
print(f"proven gap: at most {100 * (ub - lb) / lb:.1f}% above optimal")

It prints:

We know from TSPLIB that the tour’s real gap is 19.1%. The other 26 points are the weakness of the plain 1-tree, not of the tour. With the Lagrangian bound of 7,542 instead, the proven gap would be the true 19.1%, and a better upper bound from local search (Part 4) would shrink it further. Both halves matter: a branch-and-bound search prunes only when they meet.

Exercise

Redo the root of the six-stop search with the Lagrangian penalties π_B = +10 and π_H = −10 (all others 0). Recompute the modified costs of the edges at B and H, find the cheapest 1-tree, and subtract 2 · Σπ. Do you get a bound between 227 and 247?

Hint: Σπ = 0 here, so the bound is just the cost of the cheapest 1-tree under the modified costs. Start with Kruskal on {B, C, D, G, H}; D–H is now 18.

What this method can’t do yet

On six stops the plain 1-tree started 20 below the optimum, and the search needed 19 nodes. On berlin52 it starts 1,370 below, an 18.2% shortfall, and every node of the tree inherits a bound that weak. Pruning is only as good as the bounds. Better bounds, like the Lagrangian one, closed that gap here, but on larger instances some gap usually remains. Johnson, McGeoch and Rothberg (1996) found that on a wide variety of random instances the optimal tour averages less than 0.8% above the Held-Karp bound, and on TSPLIB’s real-world instances the gap is almost always under 2%. A smarter bound is worth more than any search order. The strongest bounds come from writing the TSP as an integer program and solving its linear-programming relaxation. Post 6, “Integer programming formulations”, builds those formulations.

References

• Little, J. D. C., Murty, K. G., Sweeney, D. W., and Karel, C. (1963). “An Algorithm for the Traveling Salesman Problem.” Operations Research 11(6): 972–989.
• Land, A. H., and Doig, A. G. (1960). “An Automatic Method of Solving Discrete Programming Problems.” Econometrica 28(3): 497–520.
• Held, M., and Karp, R. M. (1970). “The Traveling-Salesman Problem and Minimum Spanning Trees.” Operations Research 18(6): 1138–1162.
• Held, M., and Karp, R. M. (1971). “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Mathematical Programming 1(1): 6–25.
• Johnson, D. S., McGeoch, L. A., and Rothberg, E. E. (1996). “Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound.” Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ‘96).
• Volgenant, T., and Jonker, R. (1982). “A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem Based on the 1-Tree Relaxation.” European Journal of Operational Research 9(1): 83–89.
• Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
• Cook, W., Espinoza, D., Goycoolea, M., and Helsgaun, K. (2025). “korea81998 Computation.” University of Waterloo. https://www.math.uwaterloo.ca/tsp/korea/computation.html
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; berlin52 files and list of optimal solutions.

See the whole series · ← All writing