Traveling Salesman Problem (Branch & Bound)

Dec 8, 2025

Updated 19 hours ago

6 min read

Traveling Salesman Problem: Exact Solution via Branch and Bound

Every GPS app solves a version of this problem millions of times a day — and none of them solve it perfectly. Here's why, and how Branch and Bound gets as close as mathematically possible.

I want to start with something that sounds like a joke but isn't: the Traveling Salesman Problem (TSP) is one of the most studied problems in all of computer science, and we still don't have a fast exact solution for large inputs. Not because nobody's tried — because it's been proven that no polynomial-time algorithm likely exists.

So why are we solving it in a DAA course?

Because TSP is where Branch and Bound stops being abstract and becomes real. The bounding function isn't a hypothetical anymore — you have to actually design one, justify it, and watch it prune a search space that would otherwise be astronomical. It's the best classroom for what B&B actually does.

The Setup

A salesman needs to visit N cities and return home. The cities are connected as a complete weighted graph — every city has a direct route to every other city, each with a known cost (distance, time, toll, whatever).

$G (V, E) where every pair of vertices is connected$

For N vertices, the number of edges in a complete graph is:

\frac{N ( N - 1 )}{2}

The objective: Find a Hamiltonian cycle — a tour that visits every city exactly once and returns to the starting city — with minimum total cost.

Why Brute Force Is Hopeless

Before jumping to the algorithm, it's worth sitting with why we need B&B at all.

With N cities, the number of possible tours is:

(N - 1)!

We fix the starting city (by symmetry, it doesn't matter which one), and permute the rest.

Cities (N)	Possible Tours	Reality check
5	24	Trivial
10	362,880	Fast
15	87 billion	Slow
20	~60 trillion	Impossible
25	~310 sextillion	Universe doesn't have enough time

For N = 20, even if your computer evaluates a billion tours per second, it would take over 6 weeks to check all of them. TSP is in the class of NP-hard problems — there's no known algorithm that scales polynomially.

Branch and Bound doesn't change this worst case. But with a good bounding function, it prunes enormous chunks of the search space, making exact solutions feasible for inputs up to ~20–30 cities in practice.

The Bounding Function for TSP

This is the part most notes skip or hand-wave. The bounding function is the entire reason B&B works on TSP.

The idea: At any partial tour, compute the minimum possible cost to complete the tour from this point. If that minimum is already worse than the best complete tour found so far — prune.

A clean lower bound: Row minima reduction

For each city (row in the cost matrix), the tour must leave that city at some point. So the minimum cost edge leaving each city is a guaranteed contribution to any complete tour.

Lower Bound = \frac{1}{2} i = 1 \sum N (min_{1} (i) + min_{2} (i))

Where:

$min_{1} (i)$ = smallest edge cost leaving city $i$
$min_{2} (i)$ = second smallest edge cost leaving city $i$

We divide by 2 because each edge is counted from both endpoints.

This bound is:

Never overestimates — it's guaranteed to be ≤ the true optimal (admissible)
Fast to compute — $O (N^{2})$ scan of the matrix
Reasonably tight — prunes aggressively in practice

The Cost Matrix

TSP is represented as a cost matrix $C$ where $C [i] [j]$ is the cost of traveling from city $i$ to city $j$ .

For a symmetric TSP (most common): $C [i] [j] = C [j] [i]$

The diagonal is $\infty$ (a city can't travel to itself):

C = [\infty c_{12} c_{13} \dots c_{21} \infty c_{23} \dots c_{31} c_{32} \infty \dots ⋮ ⋮ ⋮ ⋱]

The Algorithm

plaintext

TSP_BnB(cost_matrix, N):
    Compute initial lower bound from root (all cities unvisited)
    Initialize best_tour = ∞
    Push root node to priority queue (best-first)

    while queue is not empty:
        node = pop node with lowest bound

        if node.bound >= best_tour:
            continue  // prune — can't possibly improve

        if node.level == N:
            // complete tour found
            if node.cost < best_tour:
                best_tour = node.cost
                best_path = node.path
            continue

        for each unvisited city next_city:
            child.path = node.path + [next_city]
            child.cost = node.cost + C[current][next_city]
            child.bound = compute_lower_bound(child)

            if child.bound < best_tour:
                push child to priority queue

    return best_tour, best_path

Key design choices:

Priority queue (min-heap) — always expand the node with the lowest bound first (Best-First Search)
Prune before expanding — check bound >= best_tour immediately
Update best aggressively — every complete tour found tightens the pruning threshold for everything remaining in the queue

Why Hamiltonian Cycle?

A Hamiltonian cycle visits every vertex exactly once and returns to the start. This is the constraint that makes TSP hard — it's not enough to find the shortest path, you must close the loop and cover every city.

The distinction matters algorithmically: in the state-space tree, a partial tour is only valid if:

No city is visited twice
The final step returns to the starting city

Any branch that violates (1) is infeasible → prune (backtracking-style). Any branch whose lower bound exceeds best known → prune (B&B-style).

Both pruning strategies combine in the same tree.

Complexity

	Complexity
Worst case	$O ((N - 1)!)$ — full enumeration if bound is weak
Typical case	Exponential but heavily pruned
Bound computation	$O (N^{2})$ per node
Space	$O (N^{2})$ for cost matrix + $O (N)$ for path

The honest answer: TSP via B&B has no polynomial guarantee. But for N ≤ 20 with a tight bound, it's completely practical. For N ≤ 30, it's feasible with good implementation. Beyond that, you move to heuristics (nearest neighbor, genetic algorithms, Christofides algorithm) that trade optimality for speed.

TSP vs Other B&B Problems

Problem	B&B fits because...
0/1 Knapsack	Fractional relaxation gives tight upper bound
TSP	Row-minima reduction gives tight lower bound
Job Scheduling	Greedy bound on remaining profit

TSP is the hardest of these because the state space grows as $(N - 1)!$ and the bound, while good, still leaves a large tree to explore. This is why TSP is the canonical example of an NP-hard problem that B&B handles better than brute force — but still can't crack for large N.

Quick Self-Test

Q1: For N = 6 cities, how many possible Hamiltonian tours exist?
Q2: Why do we fix the starting city when counting tours?
Q3: Why is the row-minima bound guaranteed to never overestimate the true optimal?
Q4: What's the difference between pruning an infeasible node and pruning a non-promising node in TSP?

(Answers: (6-1)! = 120. Because the tour is a cycle — starting from city A vs city B gives the same set of tours, just shifted. It sums minimum edges, which any tour must include at least — so the true cost can only be equal or higher. Infeasible = visits a city twice or breaks the cycle (backtracking prune). Non-promising = valid partial tour but bound ≥ best known (B&B prune).)

Branch and Bound Technique — the general framework this note builds on; read this first
Assignment Problem — Branch and Bound with pruning
Greedy Approach for Algorithm Design — nearest-neighbor heuristic for TSP is greedy; understand the tradeoff
Dynamic Programming & 0/1 Knapsack — Held-Karp algorithm solves TSP in $O (2^{N} \cdot N^{2})$ via DP — faster than B&B for dense graphs
Graph — TSP lives on a complete weighted graph; graph fundamentals are prerequisite
All Pairs Shortest Path (Floyd's) — Floyd-Warshall is sometimes used to preprocess TSP cost matrices
MST: Kruskal's & Prim's — MST gives a 2-approximation for TSP; key connection between exact and approximate methods
Dijkstra's Algorithm — shortest path $\neq =$ TSP tour; understanding why clarifies what makes TSP hard
Asymptotic Notation — for reading $(N - 1)!$ vs $O (2^{N})$ and understanding why factorial beats exponential in badness
Full DAA Notes Index

External References

TSP — Wikipedia — history, NP-hardness proof, and approximation algorithms
CP-Algorithms: TSP with Bitmask DP — Held-Karp implementation for competitive programming
Visualgo: TSP — animated tour construction; builds intuition before the math
CLRS Chapter 35 — approximation algorithms for NP-hard problems including TSP's 2-approximation via MST

Part of the DAA Design and Analysis series on NoteHub.