311. 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.

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

Decision variable : if the tour uses edge , else .

s.t.:

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

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

Polynomially many constraints using node potentials :

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

311.3. Computational reality

• Concorde solver (Applegate, Bixby, Chvátal, Cook): exact TSP up to 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

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

• MST lower bound: total tour length 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

311.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)

311.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

311.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