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

[github-actions[bot]]

Problem Statement

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

Concrete Instance (4-City TSP):

Suppose we have cities A, B, C, D with distances:

      A    B    C    D
  A   0   10    7    12
  B  10    0   15    20
  C   7   15    0    11
  D  12   20   11    0

Find a tour (e.g., A → C → D → B → A) that minimizes total distance. The tour above costs 7 + 11 + 20 + 10 = 48.

Input/Output:

• Input: n cities, distance matrix d[i,j]
• Output: Permutation π representing tour order; minimize Σ d[π(i), π(i+1)] for i=1..n (with wraparound)

---

Why It Matters

Real-world applications:

• Logistics & delivery: Route planning for package delivery, minimizing fuel costs and time.
• Circuit board manufacturing: Optimizing probe sequences to test circuit points; reduces equipment time.
• Tourism & travel: Planning efficient itineraries for guided tours or road trips.
• DNA sequencing: Reconstructing gene sequences by solving the shortest superstring problem (a TSP variant).

TSP appears everywhere optimization matters: from airport ground-handling to industrial robot arm motion planning.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Variables:

• succ[i] ∈ {0..n-1} — the city visited immediately after city i
• dist_total ∈ N — total tour length

Constraints:

• Each city has exactly one successor: each succ[i] is distinct (permutation)
• No subtours: use circuit(succ) global constraint to ensure a single cycle
• Distance: dist_total = Σ distance[i, succ[i]] for all i
• Objective: minimize dist_total

Advantages:

• Natural encoding; global circuit constraint has efficient filtering
• Domains shrink quickly through constraint propagation

Disadvantages:

• For large n, search space remains exponential; needs strong branching heuristics

Approach 2: Integer Linear Programming (MIP)

Variables:

• x[i,j] ∈ {0,1} — edge from city i to city j is in the tour
• u[i] ∈ R — position of city i in the tour (for subtour elimination)

Constraints:

• Degree: Σ_j x[i,j] = 1 and Σ_i x[i,j] = 1 for each city i
• Subtour elimination (Miller-Tucker-Zemlin): u[i] - u[j] + n·x[i,j] ≤ n-1 for i ≠ j
• Objective: minimize Σ distance[i,j]·x[i,j]

Advantages:

• Can leverage mature MIP solvers (CPLEX, Gurobi, SCIP)
• Linear relaxation provides lower bounds for branch-and-cut

Disadvantages:

• MTZ formulation is weaker; many LP relaxation solutions don't reduce search space efficiently
• Quadratic growth in constraints: O(n2)

---

Modeling Approaches

Example Model (MiniZinc)

% TSP in MiniZinc using circuit constraint
include "globals.mzn";

int: n = 4;
array[1..n, 1..n] of int: dist = 
  [| 0, 10,  7, 12
   |10,  0, 15, 20
   | 7, 15,  0, 11
   |12, 20, 11,  0 |];

array[1..n] of var 1..n: succ;
var int: total_dist;

constraint circuit(succ);
constraint total_dist = sum(i in 1..n)(dist[i, succ[i]]);

solve minimize total_dist;

output ["Tour: ", show(succ), "\n", "Distance: ", show(total_dist)];

---

Key Techniques

1. Global Constraint Filtering

The circuit constraint (available in CP solvers like Gecode, Choco, OR-Tools) uses graph algorithms to:

• Prune infeasible domain values early
• Detect disconnected components and subtours
• Achieve strong consistency faster than posting individual constraints

2. Branching Heuristics & Search

• Variable ordering: Prioritize cities with smallest feasible successor domains (minimum remaining values)
• Value ordering: Try nearest-neighbor edges first (greedy heuristic for direction)
• Large Neighborhood Search (LNS): After finding a solution, re-optimize by removing and reinserting k-city chains

3. Lower Bounds & Relaxation

• 1-tree bound: Compute minimum spanning tree + minimum 2-edge cover on vertices; often tight
• LP relaxation bound: Solve the degree and subtour constraints without integrality; provides optimality gap
• Chained restarts: Use bounds to guide search strategy and cutoffs

---

Challenge Corner

Open Question:
The TSP is NP-hard, but consider this variant:

Asymmetric TSP with time windows: Each city i must be visited during a time interval [e_i, l_i]. Travel between cities i and j takes t[i,j] time. Can you extend either model above to handle arrival-time constraints? How would you modify the circuit constraint or the subtour elimination to account for time feasibility?

Symmetry-breaking bonus:
The 4-city instance has rotational symmetry (A→B→C→D→A is equivalent to B→C→D→A→B). How would you add constraints to break this symmetry and reduce search space?

---

References

1. Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.

   • Gold-standard reference; covers both exact and heuristic methods.

2. Hooker, J. N. (2012). Integrated Methods for Optimization (2nd ed.). Springer.

   • Excellent chapter on modeling TSP in both CP and MIP paradigms.

3. Constraint Programming online resources:

   • MiniZinc tutorial: (www.minizinc.org/redacted) (includes TSP examples)
   • OR-Tools routing library: (developers.google.com/redacted)

4. Heuristic algorithms for TSP:

   • Lin-Kernighan algorithm; Christofides approximation algorithm—excellent starting points for practical large-scale instances.

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

• expires on Aug 31, 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 #55752.