🧩 Constraint Solving POTD:Traveling Salesman Problem (TSP)

[github-actions[bot]]

The Traveling Salesman Problem is one of the most famous problems in combinatorial optimization — deceptively simple to state, yet NP-hard to solve optimally. Today we explore how constraint solving, MIP, and hybrid approaches each take on this classic routing challenge.

---

Problem Statement

A salesman must visit n cities exactly once and return to the starting city, minimizing the total travel distance (or cost).

Concrete instance — 5 cities:

Cities: {A, B, C, D, E}  (A = depot)

Distance matrix (symmetric):
    A   B   C   D   E
A [ 0  10  15  20  25]
B [10   0  35  25  30]
C [15  35   0  30  20]
D [20  25  30   0  15]
E [25  30  20  15   0]
```

**Input:** `n` cities, pairwise distance matrix `d[i][j]`  
**Output:** A permutation `π` of cities minimizing `∑ d[π(k), π(k+1)]` (with `π(n+1) = π(1)`)

For the instance above, the optimal tour is `A → B → D → E → C → A` with total cost `10 + 25 + 15 + 20 + 15 = 85`.

---

### Why It Matters

- **Logistics & delivery:** Package routing, last-mile delivery, drone path planning — any service requiring a single vehicle visiting multiple stops is a TSP at its core.
- **Manufacturing:** Printed circuit board drilling (minimizing head movement), CNC machining tool paths, and genome sequencing (ordering DNA fragments) all reduce to TSP variants.
- **Healthcare:** Optimizing the route of a mobile clinic or field technician visiting patients maps directly to this problem.

---

### Modeling Approaches

#### Approach 1: Mixed-Integer Programming (MIP) — Miller-Tucker-Zemlin formulation

The MIP approach introduces **subtour elimination constraints** to ensure one connected tour.

**Decision variables:**
- `x[i][j] ∈ {0,1}` — 1 if the tour traverses edge `(i,j)`
- `u[i] ∈ {1..n}` — position of city `i` in the tour (auxiliary, for subtour elimination)

**Model:**
```
minimize  ∑_{i,j} d[i][j] · x[i][j]

subject to:
  ∑_j x[i][j] = 1        ∀i   (leave each city once)
  ∑_i x[i][j] = 1        ∀j   (enter each city once)
  u[i] - u[j] + n·x[i][j] ≤ n-1   ∀i≠j, i,j ≥ 2  (MTZ subtour elimination)
  x[i][j] ∈ {0,1},  u[i] ≥ 1
```

**Trade-offs:** Easy to hand off to any MIP solver (Gurobi, CPLEX, HiGHS). The MTZ constraints are weak (poor LP relaxation), but the Dantzig–Fulkerson–Johnson (DFJ) formulation with exponential subtour cuts gives a much tighter relaxation when used with branch-and-cut.

---

#### Approach 2: Constraint Programming (CP)

CP models TSP naturally using **successor variables** and the `circuit` global constraint.

**Decision variables:**
- `next[i] ∈ {1..n}` — the city visited immediately after city `i`

**Model:**
```
minimize  ∑_i d[i][next[i]]

subject to:
  circuit(next)          // global constraint: next[] forms a single Hamiltonian circuit
  // Objective bound via cost array lookup:
  cost[i] = d[i][next[i]]   ∀i

Trade-offs: The circuit constraint performs propagation equivalent to shortest-path reasoning (e.g., filtering based on 1-tree bounds in some solvers). Very expressive — easy to add side constraints (time windows, capacity). Scales less well to large pure TSP instances than dedicated MIP branch-and-cut, but shines when combined with side constraints.

Example Model (OR-Tools CP-SAT, Python)

from ortools.sat.python import cp_model

def solve_tsp(n, dist):
    model = cp_model.CpModel()

    # next[i] = city visited after city i
    next_city = [model.NewIntVar(0, n - 1, f'next_{i}') for i in range(n)]

    # Each city visited exactly once — circuit constraint
    # OR-Tools AddCircuit takes (tail, head, literal) arcs
    arcs = []
    arc_costs = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                lit = model.NewBoolVar(f'arc_{i}_{j}')
                arcs.append((i, j, lit))
                arc_costs[(i, j)] = lit
    model.AddCircuit(arcs)

    # Objective: minimize total distance
    obj_terms = [dist[i][j] * arc_costs[(i, j)]
                 for i in range(n) for j in range(n) if i != j]
    model.Minimize(sum(obj_terms))

    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f'Tour cost: {solver.ObjectiveValue()}')

---

Key Techniques

1. Lower Bounding via 1-Tree Relaxation

A minimum spanning tree on n-1 cities plus the two cheapest edges incident to the depot gives a Held-Karp lower bound — often within 1–2% of optimal. This bound drives branch-and-bound pruning and guides CP propagation through the circuit constraint in many solvers.

2. Symmetry Breaking

TSP tours have two trivial symmetries: direction (A→B→C and A→C→B are the same tour) and starting point (any rotation is equivalent). Fixing city 0 as the first node and requiring next[0] < prev[0] (or equivalent) cuts the search space by 2n.

3. Large Neighbourhood Search (LNS) / Lin-Kernighan Moves

For large instances (n > 1000), exact methods are impractical. LNS destroys part of the current solution (e.g., removes 3 random edges) and repairs it optimally. The Lin-Kernighan heuristic iteratively applies k-opt moves — swapping k edges — and is the foundation of the world-class LKH solver. Hybrid approaches use LNS as a metaheuristic driving a CP or MIP subproblem.

---

Challenge Corner

Symmetry puzzle: For the standard symmetric TSP on n cities, the search space has (n-1)!/2 distinct tours. After fixing the starting city, you still have (n-1)! orderings. What additional constraint on the next[] array (or on a position variable pos[]) would enforce directional symmetry breaking and halve this space? Can you express it in a single constraint?

Bonus: the Asymmetric TSP (ATSP) has d[i][j] ≠ d[j][i]. How does this break the directional symmetry, and what subtour elimination technique is most effective for ATSP?

---

References

1. Applegate, Bixby, Chvátal & Cook — The Traveling Salesman Problem: A Computational Study (Princeton, 2006). The definitive reference, covering branch-and-cut, LP relaxations, and the Concorde solver.
2. Helsgott, Keld & Lin — An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research 21(2), 1973. The original Lin-Kernighan paper.
3. OR-Tools TSP Tutorial — [developers.google.com/optimization/routing/tsp]((developers.google.com/redacted) Practical Python guide using OR-Tools' routing library.
4. Rossi, van Beek & Walsh — Handbook of Constraint Programming, Chapter 20 (Routing). Covers CP-based approaches to TSP and VRP with global constraints.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 8, 2026, 1:02 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #24106.