🧩 Constraint Solving POTD:Problem of the Day: Traveling Salesman Problem

[github-actions[bot]]

Problem Statement

Given a set of cities and the distance between every pair, find the shortest tour that visits each city exactly once and returns to the start. This is the Traveling Salesman Problem (TSP).

Small instance (5 cities, symmetric distances):

	A	B	C	D	E
A	0	2	9	10	7
B	2	0	6	4	3
C	9	6	0	8	5
D	10	4	8	0	6
E	7	3	5	6	0

• Input: n and an n × n distance matrix d.
• Output: a cyclic permutation of the cities minimising total distance.

For this instance the optimum is 26, reached by two tours: A→B→D→C→E→A and A→B→D→E→C→A (reverses of each other are the same tour, so the true count is 12 undirected tours, which we verified by enumeration).

Why It Matters

• Logistics and delivery: last-mile routing and drone or courier planning are TSP variants at heart.
• Manufacturing: the tool path for drilling circuit boards or moving a laser head is a TSP, and shorter paths directly save machine time.
• Bioinformatics: ordering DNA fragments during sequence assembly is closely related to finding a short Hamiltonian path.

Modeling Approaches

1. Constraint Programming with a circuit global

• Variables: succ[i] ∈ {1..n}, the city visited immediately after city i.
• Constraints: circuit(succ) requires the successor links to form a single Hamiltonian cycle (no self-loops, no subtours).
• Objective: min Σi d[i, succ[i]].
• Trade-offs: propagation is strong. The circuit propagator tracks chains of fixed successors and prunes any value that would close a subtour early. Scaling is limited without extra bounding, so it works well for small and medium instances.

Example Model (MiniZinc pseudo-code)

int: n = 5;
array[1..n, 1..n] of int: d = [| 0, 2, 9, 10, 7
                               | 2, 0, 6, 4, 3
                               | 9, 6, 0, 8, 5
                               | 10, 4, 8, 0, 6
                               | 7, 3, 5, 6, 0 |];
array[1..n] of var 1..n: succ;   % succ[i] = city visited right after i
constraint circuit(succ);        % one Hamiltonian cycle, no subtours
var int: cost = sum(i in 1..n)(d[i, succ[i]]);
solve minimize cost;

2. MIP with Miller–Tucker–Zemlin (MTZ) subtour elimination

• Variables: binary x_ij (1 if the tour goes i → j), and integer position u_i ∈ {2..n} for i ≥ 2.
• Constraints:
  • Σj x_ij = 1 and Σi x_ij = 1 (each city has one outgoing and one incoming arc).
  • u_i − u_j + n·x_ij ≤ n − 1 for i ≠ j, i, j ≥ 2 (forbids subtours).
• Objective: min Σij d_ij · x_ij.
• Trade-offs: the model is compact (O(n2) constraints) and is easy to extend. Its LP relaxation is weak, so the bound is loose. The stronger alternative is branch-and-cut with lazily added subtour-elimination cuts, which is how Concorde solves instances with thousands of cities.

Key Techniques

1. Global constraint filtering. A circuit propagator is far stronger than decomposing into alldifferent plus clauses that forbid subtours, because it reasons about reachability across the whole chain structure.
2. Relaxation-based bounding. The assignment problem (drop the single-cycle requirement) gives a lower bound. Reduced costs from its LP can prune domain values in CP through cost-based filtering, and Held–Karp 1-trees give tighter bounds.
3. Large Neighbourhood Search (LNS). Start from a nearest-neighbour tour, then repeatedly unfix a random subset of succ variables and re-solve the small subproblem. Pair this with 2-opt or Or-opt moves for fast, high-quality heuristic solutions.

Challenge Corner

• Symmetry: distances are symmetric, so every tour appears in two directions. Which single constraint on succ removes the reversed duplicates without cutting off any optimal tour?
• Fewer variables: can you replace the n2 binaries in the MTZ model with a single-commodity flow formulation? How many constraints does it need, and how does its LP bound compare?
• Extension: give each city a time window [ai, bi]. How does the MTZ model change? How would a CP solver use the windows in propagation, for example with interval variables?

References

• Applegate, Bixby, Chvátal & Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. The standard reference for exact TSP methods and Concorde.
• Rossi, van Beek & Walsh (eds.), Handbook of Constraint Programming, Elsevier, 2006. Covers global constraints and filtering.
• Miller, Tucker & Zemlin, "Integer Programming Formulation of Traveling Salesman Problems," Journal of the ACM, 7(4), 1960. The original MTZ formulation.
• Laporte, "The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms," European Journal of Operational Research, 1992. An accessible survey.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~2 AIC · ⌖ ~2 AIC · ⊞ 3.2K · ◷

• expires on Nov 15, 2026, 3:33 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 #76225.