🧩 Constraint Solving POTD:Problem of the Day: The Traveling Salesman Problem (TSP)

[github-actions[bot]]

Problem Statement

The Traveling Salesman Problem asks: given a set of cities and the distances between them, find the shortest route that visits every city exactly once and returns to the starting city.

Concrete Instance: Consider 5 cities {A, B, C, D, E} with symmetric distances:

     A    B    C    D    E
A    0    10   15   20   25
B    10   0    35   25   15
C    15   35   0    30   10
D    20   25   30   0    14
E    25   15   10   14   0

Find a tour through all 5 cities with minimum total distance. For example, the tour A → B → E → D → C → A has cost 10 + 15 + 14 + 30 + 15 = 84.

Input: Complete graph with n vertices and edge weights d[i,j]
Output: A permutation of cities forming a tour with minimum total distance

Why It Matters

Delivery route optimization: Logistics companies use TSP solvers daily to plan package delivery routes for drivers, reducing fuel costs and delivery times across thousands of routes worldwide.

Printed circuit board drilling: Manufacturers must drill holes in PCBs efficiently; the order of drill positions directly impacts production time—TSP determines the drilling sequence.

DNA sequencing: In genome assembly, TSP helps order DNA fragments to minimize the cost of reconstructing genomes from short sequencing reads.

Airport scheduling: Airlines optimize the sequence of aircraft maintenance tasks to minimize equipment downtime and hangar congestion.

Modeling Approaches

Approach 1: Constraint Programming (Subtour Elimination)

Paradigm: Integer Programming with logic-based constraints

Variables: x[i,j] ∈ {0,1}    (binary: visit edge from city i to j)
           u[i] ∈ {1..n}     (subtour breaking: position in tour)

Minimize:  Σ d[i,j] · x[i,j]

Constraints:
  • Each city has exactly one outgoing edge:  Σ_j x[i,j] = 1  ∀i
  • Each city has exactly one incoming edge:  Σ_i x[i,j] = 1  ∀j
  • Subtour elimination (Miller-Tucker-Zemlin):
    u[i] - u[j] + n·x[i,j] ≤ n-1  ∀i≠j, i,j ∈ {2..n}
  • Position bounds: 1 ≤ u[i] ≤ n  ∀i

Trade-offs: Simple formulation with polynomial number of constraints. The MTZ inequalities are weak (loose LP relaxation) but easy to implement. Works well for n ≤ 50 in practice.

Approach 2: Constraint Programming (Circuit Constraint + Search)

Paradigm: Pure CP with global constraints

Variables: next[i] ∈ {0..n-1}   (next city in tour after city i)
           cost[i] ∈ R+         (cost of edge from i to next[i])

Minimize:  Σ cost[i]

Constraints:
  • Circuit:  all-different(next[1..n]) ∧ connected_cycle(next)
              (enforces a single cycle visiting all cities exactly once)
  • Cost linking:  cost[i] = d[i, next[i]]  ∀i
  • Optional:  sym_break: next[0] < next[n-1]  (break symmetry)

Trade-offs: The circuit global constraint encodes subtour elimination directly via sophisticated propagation (faster pruning than MTZ inequalities). Requires a CP solver (OR-Tools, Gurobi, Chuffed). Excellent for large instances (n ≥ 100) when paired with search heuristics.

Approach 3: Local Search Heuristic

Paradigm: Metaheuristic/neighborhood exploration

Initialize: random tour τ
Repeat:
  For each pair of edges (i,j) and (k,l) in τ:
    Compute Δ = d[i,k] + d[j,l] - (d[i,j] + d[k,l])
    If Δ < 0 (improvement found):
      Reverse the path between j and k in τ
      Update cost
      (2-opt move)
  Until no improving move exists → return local optimum

Trade-offs: No optimality guarantee, but finds high-quality solutions in seconds for instances with thousands of cities. Combines simplicity with impressive practical performance. Often seeded with a construction heuristic (nearest neighbor, Christofides).

Example: OR-Tools TSP Solver (Python)

from ortools.linear_solver import pywraplp

# Create the linear solver with CBC backend
solver = pywraplp.Solver.CreateSolver('CBC')

n = 5  # number of cities
dist = [[0, 10, 15, 20, 25],
        [10, 0, 35, 25, 15],
        [15, 35, 0, 30, 10],
        [20, 25, 30, 0, 14],
        [25, 15, 10, 14, 0]]

# Decision variables: x[i][j] = 1 if we travel from city i to j
x = {}
for i in range(n):
    for j in range(n):
        if i != j:
            x[i, j] = solver.IntVar(0, 1, f'x[{i},{j}]')

# Flow variables for subtour elimination
u = [solver.IntVar(1, n, f'u[{i}]') for i in range(n)]

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

# Each city has exactly one outgoing edge
for i in range(n):
    solver.Add(sum(x[i, j] for j in range(n) if i != j) == 1)

# Each city has exactly one incoming edge
for j in range(n):
    solver.Add(sum(x[i, j] for i in range(n) if i != j) == 1)

# Subtour elimination (MTZ constraints)
for i in range(1, n):
    for j in range(1, n):
        if i != j:
            solver.Add(u[i] - u[j] + n * x[i, j] <= n - 1)

# Solve
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print(f"Optimal tour cost: {solver.Objective().Value()}")

Key Techniques

1. Cutting Planes & Constraint Strengthening
The basic subtour elimination formulation has a weak LP relaxation (can be far from the integer optimum). Solvers add cutting planes (Gomory cuts, Chvátal-Gomory cuts) to strengthen bounds. For TSP specifically, comb inequalities and blossom inequalities are particularly effective but computationally expensive. Branch-and-cut algorithms alternate between solving LP relaxations and adding cuts.

2. Search Heuristics: Variable & Value Ordering
When solving TSP via CP/search, the choice of which city to visit next is critical:

• Nearest Neighbor Heuristic: Greedily visit the closest unvisited city (fast but suboptimal).
• Minimum Slack: Choose the edge with smallest distance - LP_relaxation_value to guide search toward proven optimal edges.
• Restart Strategies: When search hits a plateau, restart from a new random initial tour (helps escape bad decisions early).

3. Lower Bounds & Relaxation
Tight lower bounds prune the search tree efficiently:

• Held-Karp Bound: Compute a lower bound using Lagrangian relaxation of degree constraints (~1–2% from optimum for many instances).
• LP Relaxation: The continuous relaxation of the IP model (without integrality) provides a lower bound; branch-and-cut refines it.
• MST Lower Bound: The minimum spanning tree is a lower bound on TSP cost (easily computed, often loose).

Challenge Corner

Open Question for You:

Suppose you are solving a dynamic TSP where the customer locations and distances change over time (e.g., real-time delivery requests). Classical exact algorithms recompute from scratch, which is slow. How would you design a warm-start strategy that reuses solutions from the previous time step? Consider:

• Which cities' positions in the tour are most likely to remain optimal?
• How would you detect when the old tour is "invalidated" and re-optimization is necessary?
• Could you use machine learning to predict which edges will remain in future optimal tours?

References

1. Applegate, D., Bixby, R., Chvátal, V., Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
   → The definitive reference on modern TSP solving techniques, including branch-and-cut algorithms.

2. Croes, G. A. (1958). "A method for solving traveling-salesman problems." Operations Research, 6(6), 791–812.
   → Classic paper introducing the 2-opt local search heuristic.

3. Miller, C. E., Tucker, A. W., Zemlin, R. A. (1960). "Integer programming formulations and traveling salesman problems." Journal of the ACM, 7(4), 326–329.
   → Introduces the Held-Karp (MTZ) subtour elimination formulation.

4. Google OR-Tools TSP Documentation: (developers.google.com/redacted)
   → Practical guide with code examples for solving vehicle routing (generalization of TSP).

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.3 AIC · ⌖ 8.27 AIC · ⊞ 6.2K · ◷

• expires on Sep 1, 2026, 3:39 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #56013.