Lab 10 — Exact TSP: Held-Karp & Branch-and-Bound

Goal

Solve the Traveling Salesman Problem exactly: Held-Karp bitmask DP in O(n² · 2^n) for n ≤ 20, and understand the branch-and-bound ladder that extends exact solving to n ≈ 30–40 and (with LP machinery) to tens of thousands of cities.

Background

TSP: given pairwise distances between n cities, find the cheapest tour visiting each exactly once and returning to start. NP-hard; the naive answer is (n−1)! permutations.

Held & Karp (1962), independently Bellman: DP over subsets.

dp[S][j] = min cost of a path that starts at city 0, visits exactly
           the cities in set S, and ends at city j ∈ S
dp[{0,j}][j]  = dist[0][j]
dp[S][j]      = min over k ∈ S∖{j} of dp[S∖{j}][k] + dist[k][j]
answer        = min over j of dp[full][j] + dist[j][0]

The win: 20! ≈ 2.4 × 10^18 → 20² × 2^20 ≈ 4.2 × 10^8. Exponential, but a tractable exponential — and it’s the fastest known exact algorithm with a worst-case guarantee.

Branch-and-bound: DFS over partial tours, pruning any branch whose cost + an admissible lower bound on the remainder ≥ best complete tour so far. Bound ladder, weak → strong: sum of cheapest edges per unvisited city → MST of unvisited cities → Held-Karp 1-tree bound with Lagrangian penalties. Concorde (LP relaxation + cutting planes + B&B) has solved instances of 85,900 cities — NP-hardness is about worst cases, not typical ones.

Interview Context

  • Standard FAANG: yes, disguised — Find the Shortest Superstring (LC 943), Minimum Cost to Visit Every Node, Parallel Courses II (LC 1494); “N ≤ 20” in any problem statement is a bitmask-DP siren
  • Codeforces / ICPC: bitmask-DP-over-subsets is a permanent fixture
  • OR / logistics / routing companies (Amazon transportation, Uber, FedEx-adjacent): the real thing, plus heuristics
  • Quant: occasional, as assignment/sequencing subproblems

When to Skip This Topic

Skip if any of these are true:

  • Phase 3 Lab 08 / Phase 5 Lab 10 (bitmask DP) aren’t solid — this is their capstone, not an alternative entry point
  • You only need approximate routing knowledge — read the Christofides bullet in Follow-ups and move on

The Held-Karp half is genuinely interview-relevant; the branch-and-bound half is domain knowledge for solver/OR roles.

Problem Statement

Minimum Cost Hamiltonian Cycle.

Given an n × n matrix dist (dist[i][j] ≥ 0, not necessarily symmetric), return the minimum cost of a tour starting and ending at city 0 that visits every city exactly once — and the tour itself. Interviewers nearly always follow up asking for the tour; build reconstruction in from the start.

Constraints

  • n ≤ 20 (DP); discussion expected for n = 30 (B&B) and n = 10^4 (heuristics)
  • Weights ≤ 10^6, so path sums fit comfortably in int64
  • Time: n = 20 in a few seconds in Python, < 1 sec compiled

Clarifying Questions

  1. Return to the start, or end anywhere? (Cycle here; a path variant just drops the closing edge — changes the final min.)
  2. Symmetric distances? Triangle inequality? (Neither needed for DP; both needed for Christofides.)
  3. Is the graph complete? (If not, missing edges = ∞; detect unreachable answer.)
  4. One optimal tour or all? (One.)
  5. n’s actual bound? (The entire algorithm choice hangs on it: ≤ 20 DP, ≤ ~35 B&B, beyond → heuristics.)

Examples

4 cities:

dist = [[0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]]

DP table (masks containing city 0; showing reachable (mask, last) states):

dp[{0,1}][1] = 10      dp[{0,2}][2] = 15      dp[{0,3}][3] = 20
dp[{0,1,2}][2] = 45    dp[{0,1,2}][1] = 50
dp[{0,1,3}][3] = 35    dp[{0,1,3}][1] = 45
dp[{0,2,3}][3] = 45    dp[{0,2,3}][2] = 50
dp[full][1] = 70   dp[full][2] = 65   dp[full][3] = 75
answer = min(70+10, 65+15, 75+20) = 80
tour: 0 → 1 → 3 → 2 → 0

Brute Force

Fix city 0 as start; try all (n−1)! orderings of the rest; keep the cheapest.

Brute Force Complexity

  • Time: O(n!) — n = 13 is already ~5 × 10^9 tour evaluations
  • Space: O(n)

Optimization Path

  1. Notice the repeated work: many permutations share (set of visited cities, current city) — that pair is the entire relevant state. → dp[mask][last].
  2. Iterate masks in increasing order (every subset precedes its supersets numerically) — no recursion needed.
  3. Only masks containing bit 0; halves the table.
  4. Parent table par[mask][last] = k for tour reconstruction.
  5. For n > 20: switch paradigms to branch-and-bound — DFS partial tours, prune with best-so-far + MST-based lower bound on unvisited remainder.

Final Expected Approach

from math import inf

def held_karp(dist):
    n = len(dist)
    size = 1 << n
    dp = [[inf] * n for _ in range(size)]
    par = [[-1] * n for _ in range(size)]
    dp[1][0] = 0

    for mask in range(1, size):
        if not mask & 1:
            continue
        for last in range(n):
            if not mask >> last & 1 or dp[mask][last] == inf:
                continue
            base = dp[mask][last]
            for nxt in range(n):
                if mask >> nxt & 1:
                    continue
                nmask = mask | 1 << nxt
                cand = base + dist[last][nxt]
                if cand < dp[nmask][nxt]:
                    dp[nmask][nxt] = cand
                    par[nmask][nxt] = last

    full = size - 1
    best, best_end = inf, -1
    for last in range(1, n):
        cand = dp[full][last] + dist[last][0]
        if cand < best:
            best, best_end = cand, last

    tour, mask, cur = [], full, best_end
    while cur != -1:
        tour.append(cur)
        mask, cur = mask ^ (1 << cur), par[mask][cur]
    tour.reverse()
    return best, tour + [0]

Forward-relaxation formulation (push from mask to mask | bit) shown — it visits each transition once and skips unreachable states naturally. The pull formulation from Background is equivalent.

B&B sketch for the discussion round: DFS over partial tours; bound = cost so far + cheapest edge into each unvisited city (admissible because every unvisited city must be entered exactly once); upgrade to MST of {unvisited ∪ current ∪ start} for far stronger pruning; seed best-so-far with a greedy nearest-neighbor tour so pruning bites from the first branch.

Data Structures

  • dp: 2^n × n array of int64 (n = 20 → ~84 MB as Python lists; use array/numpy if memory-pressed)
  • par: same shape, for reconstruction
  • Bitmask ints as visited sets
  • B&B: recursion stack + current best (and a DSU or heap if building MST bounds per node)

Correctness Argument

  • State sufficiency: the cheapest completion of a partial tour depends only on (visited set, current city) — not the order visited. So collapsing permutations into dp[mask][last] loses nothing.
  • Induction over |mask|: assuming dp is exact for all masks of size k, every size-k+1 state is reached by extending some exact size-k state with one edge, and the min over predecessors is exact. Base dp[{0}][0] = 0.
  • Iterating masks in increasing numeric order is a valid topological order: mask ⊂ nmask ⟹ mask < nmask.
  • B&B correctness: it only discards branches whose admissible lower bound already exceeds a known achievable tour — no optimal solution can be pruned.

Complexity

  • Held-Karp time: O(n² · 2^n); n = 20 → ~4.2 × 10^8 transitions (seconds in Python, fast in C)
  • Space: O(n · 2^n) — 20 M entries at n = 20; this, not time, is often the binding constraint
  • B&B: worst case still exponential; strong bounds make n = 30–40 practical
  • Approximation for large n: Christofides O(n³), guarantee 1.5× on metric instances

Implementation Requirements

  • Skip masks without bit 0 and unreachable states (dp == inf) — the inner-loop constant matters at 4 × 10^8 ops
  • int64 discipline in compiled languages: 20 × 10^6 path sums exceed int32
  • Parent table maintained in the same relaxation that improves dp — reconstruction from a separate pass is a common source of mismatched tours
  • Asymmetric input must be handled (no dist[i][j] == dist[j][i] assumption anywhere)
  • Path variant (Shortest Superstring): answer = min dp[full][j] with no closing edge — don’t hardcode the cycle close

Tests

  • The 4-city example → 80, tour [0, 1, 3, 2, 0] (or its reverse for symmetric input)
  • n = 2 → 2 × dist[0][1]; n = 1 → 0
  • Asymmetric instance where forward and reverse tours differ — verifies no symmetry assumption
  • Random n = 10 vs brute-force permutation oracle: costs equal, tour validates (each city once, cost re-adds correctly)
  • All-equal weights → any permutation optimal; assert cost = n × w
  • Missing edges (∞): unreachable instance reports ∞/None rather than garbage
  • n = 20 performance run

Follow-up Questions

  • How do you return the tour, not just the cost? → Parent pointers per state (shown), O(n·2^n) extra memory; or re-derive each step by checking which predecessor achieves dp equality, O(n²) time per step with zero extra memory. Know both — interviewers ask for the memory-free version when dp is already at the limit.
  • Can you halve the memory? → Yes: fix city 1’s side of the tour orientation for symmetric TSP, or store only masks containing bit 0 with index remapping (mask >> 1). Rolling the dp by mask popcount layers also works: keep only layers k and k+1 if you don’t need reconstruction.
  • Shortest Superstring (LC 943) connection? → Overlap graph: dist[i][j] = len(word j) − overlap(i, j); answer is a Hamiltonian path, not cycle — drop the closing edge and take min over all (start, end).
  • Why is the MST a valid lower bound for B&B? → Removing one edge from any tour of the unvisited remainder leaves a spanning tree of it; MST ≤ that tree ≤ tour remainder. The stronger Held-Karp 1-tree bound adds back one vertex with its two cheapest edges and sharpens with Lagrangian node penalties — typically within 1–2% of optimal.
  • What when n = 10^5? → Exact is off the table without Concorde-class LP machinery. Practical stack: nearest-neighbor or greedy construction, then 2-opt/3-opt local search, then Lin-Kernighan (LKH routinely lands within 1% on huge instances). Christofides gives the 1.5 guarantee on metric instances but LKH beats it in practice.
  • Where else does the dp[subset][last] shape appear? → Any “sequence over a small set with pairwise interaction cost”: job scheduling with setup times, LC 847 (shortest path visiting all nodes — BFS variant), LC 1434, assignment problems, and Kociemba-style solvers use the sibling trick of dp over coordinates (lab-02).

Product Extension

  • Last-mile delivery routing (per-vehicle stop sequencing after cluster assignment)
  • PCB drill-path and pick-and-place head sequencing (classic Concorde application domains)
  • Warehouse picker pathing; AGV tour planning
  • Genome assembly’s superstring heart (LC 943 is a toy of it)
  • Chip design: TSP-shaped subproblems in routing and scan-chain ordering

Language/Runtime Follow-ups

  • Python: the mask loops are pure-Python slow at n = 20 (~minutes naive); mitigate with the inf-skip, or numpy per-mask vectorization, or accept n ≤ 17 in-interview and say so — stating the constant-factor reality is a signal, not a failure.
  • C++: flat vector<int64_t> dp, index = mask*n + last; n = 20 in well under a second.
  • Java: long[1<<n][n]; beware autoboxing if reaching for collections — don’t.
  • Go: straightforward; slices of int64, no surprises.

Common Bugs

  1. Start city not fixed: iterating tours from every start multiplies work by n and breaks reconstruction; fixing city 0 is WLOG for cycles.
  2. Closing edge forgotten (or added in the path variant): answer off by one edge — the single most common bug in this problem.
  3. Masks without bit 0 processed: wrong states get relaxed and reconstruction walks into them.
  4. Parent recorded outside the improving branch: tour disagrees with cost; always update par in the same if cand < dp body.
  5. int32 overflow in compiled languages at max weights.
  6. Reconstruction mask bookkeeping: must remove cur’s bit before looking up the parent’s mask entry — par[mask][cur] is indexed by the mask that still contains cur; mixing the two orders yields plausible-looking wrong tours.

Debugging Strategy

  • Brute-force permutation oracle for n ≤ 10; assert equal costs on 100 random matrices
  • Validate returned tours independently: n+1 nodes, starts/ends at 0, each city once, edges re-sum to the reported cost
  • Print dp layer by popcount for the 4-city example and diff against the hand table above
  • For B&B: assert bound ≤ true completion cost on random partial tours (admissibility test); count pruned vs explored nodes
  • Asymmetric test matrices catch silent transposition bugs (dist[k][j] vs dist[j][k])

Mastery Criteria

  • Write Held-Karp with reconstruction from memory in ≤ 30 min
  • State the state-sufficiency argument (why (mask, last) is enough) in ≤ 2 min
  • Recite the n → algorithm ladder: ≤ 20 DP, ≤ ~35 B&B, large → LKH/Christofides, and why
  • Recognize disguised Hamiltonian-path DPs (LC 943/847/1494) on sight
  • Explain the MST bound’s admissibility and name the 1-tree improvement
  • Estimate memory for dp at a given n before writing code