TSP

314. TSP

The Traveling Salesman Problem: visit $𝑛$ cities exactly once and return to start, minimizing total distance.

Famous for being easy to state, hard to solve: NP-hard, no known polynomial-time exact algorithm. But also one of the most-studied problems in combinatorial optimization.

314.1. Formulation (DFJ — Dantzig-Fulkerson-Johnson, 1954)

Decision variable $𝑥_{𝑖 𝑗} \in {0, 1}$ : $1$ if the tour uses edge $(𝑖, 𝑗)$ , else $0$ .

min \sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

s.t.:

\sum_{𝑗} 𝑥_{𝑖 𝑗} = 1, \forall 𝑖 (leave each city once)

\sum_{𝑖} 𝑥_{𝑖 𝑗} = 1, \forall 𝑗 (enter each city once)

\sum_{𝑖 \in 𝑆, 𝑗 \notin 𝑆} 𝑥_{𝑖 𝑗} \geq 1, \forall 𝑆 \subset 𝑉, 2 \leq | 𝑆 | \leq 𝑛 - 1 (subtour elimination)

𝑥_{𝑖 𝑗} \in {0, 1}

The subtour-elimination constraints are exponential in number ( $2^{𝑛} - 2$ subsets). In practice, add them lazily as cutting planes when violated.

314.2. Alternative formulation (MTZ — Miller-Tucker-Zemlin)

Polynomially many constraints using node potentials $𝑢_{𝑖}$ :

𝑢_{𝑖} - 𝑢_{𝑗} + 𝑛 𝑥_{𝑖 𝑗} \leq 𝑛 - 1, \forall 𝑖, 𝑗 \in {2, \dots, 𝑛}, 𝑖 \neq 𝑗

Forces a single tour without exponentially many cuts. LP relaxation is weaker than DFJ, so fewer cuts needed but worse bounds.

314.3. Computational reality

Concorde solver (Applegate, Bixby, Chvátal, Cook): exact TSP up to $\sim 85, 000$ cities
Practical heuristics (LKH-3, OR-tools): near-optimal solutions for millions of cities in minutes
NP-hard — but the constants are favorable in practice

314.4. Lower bounds (for branch-and-bound)

MST lower bound: total tour length $\geq$ MST weight (twice the MST = upper bound, see Christofides)
1-tree bound (Held-Karp): drop one node, MST on the rest, plus the two cheapest edges from the dropped node
LP relaxation of DFJ

314.5. Heuristics

Nearest neighbor: start anywhere, go to the closest unvisited city. Bad — often 25% above optimal
Greedy edge: keep adding cheapest edge that doesn’t create a cycle (until tour complete). Bad — similar quality
Insertion heuristics: build tour by inserting one city at a time (cheapest, nearest, farthest)
2-opt, 3-opt: local search swapping pairs / triples of edges — see TSP 2-opt
Lin-Kernighan: variable-depth swap; the gold standard for heuristic TSP
Christofides: 1.5-approximation for metric TSP (triangle inequality)

314.6. Variants

Symmetric TSP: $𝑐_{𝑖 𝑗} = 𝑐_{𝑗 𝑖}$ — most studied
Asymmetric TSP (ATSP): different costs each direction
Euclidean TSP: cities are points in the plane; admits PTAS (Arora 1998)
Metric TSP: triangle inequality; 1.5-approx by Christofides
Vehicle Routing Problem (VRP): multiple vehicles, capacities — see VRP

314.7. See also

TSP 2-opt — local search heuristic
Christofides — 1.5-approximation
VRP — multi-vehicle generalization
Clarke-Wright Savings — heuristic
MST — used in lower bounds