Completed · Corrected repeated benchmark · C99/MPI
Distributed TSP Solver
A distributed-memory parallel-tempering solver with TSPLIB-compatible EUC_2D route weights, deterministic seed support, official Berlin52 optimal-tour validation, and a repeated strong-scaling study on the Stromboli cluster.
Problem
The Traveling Salesman Problem has a rapidly growing search space. Distributed optimization can reduce search time, but it introduces communication, synchronization, load-distribution, stochastic variability, and benchmarking challenges.
My contribution
- Implemented distributed parallel tempering using C99 and MPI.
- Used two-opt route modifications with Metropolis acceptance.
- Precomputed a distance matrix for constant-time edge-weight lookups.
- Designed an alternating neighboring-rank exchange pattern.
- Corrected the objective to use the TSPLIB
EUC_2Dnearest-integer convention. - Added an official optimal-tour fixture, deterministic seeds, automated MPI validation, repeated timing, and archived cluster provenance.
Metric correction
The Berlin52 instance declares EDGE_WEIGHT_TYPE: EUC_2D. The corrected implementation rounds each Euclidean edge length to the nearest integer before summing the route weight. The included official optimal tour is evaluated in CI and must equal 7542. Earlier course outputs used raw floating-point Euclidean distances, so their route-quality values are not directly comparable with the official TSPLIB optimum.
Parallel methodology
Search
Replicas at different temperatures balance local improvement with wider exploration.
Communication
Neighboring replicas exchange routes through an ordered alternating pattern.
Reproducibility
The benchmark uses fixed base seeds and records the process count, runtime, route length, speedup, efficiency, and variability.
Corrected repeated benchmark
The Stromboli study used five fixed seeds—1001, 2002, 3003, 4004, and 5005—at 1, 2, 4, 8, 12, and 24 MPI processes. This produced 30 measured runs. Every run reached the official Berlin52 optimum of 7542.
| MPI processes | Median runtime [s] | Median speedup | Parallel efficiency |
|---|---|---|---|
| 1 | 6.8956 | 1.000 | 100.0% |
| 2 | 3.5857 | 1.923 | 96.2% |
| 4 | 1.9133 | 3.604 | 90.1% |
| 8 | 1.0907 | 6.322 | 79.0% |
| 12 | 0.8497 | 8.116 | 67.6% |
| 24 | 0.6367 | 10.830 | 45.1% |
The raw and aggregated datasets are archived in the repository benchmark directory. Median runtime is used because repeated stochastic runs are better represented by a robust central value than by one isolated timing.
Automated evidence
- The production C99/MPI solver must compile with OpenMPI.
- The official Berlin52 tour must evaluate to the TSPLIB weight
7542. - A reduced deterministic two-rank smoke case must complete without hanging.
- The generated route must contain each of the 52 cities exactly once.
Historical course benchmark
The original course study reported a 20.7× speedup and approximately 86% parallel efficiency on 24 cores. Those plots are retained only as historical artifacts because the earlier implementation used raw floating-point distances. They must not be compared directly with the corrected benchmark above.
Scope and limitations
- The parser currently supports coordinate instances using TSPLIB
EUC_2D. - The global replica count and temperature schedule remain compile-time settings.
- The corrected benchmark represents one problem instance and one cluster environment.
- Performance remains dependent on hardware, compiler, MPI version, process mapping, and random seed.
Next extensions
Useful extensions include runtime configuration of replica count and temperature schedule, additional TSPLIB instances, hybrid MPI/OpenMP execution, and comparison across multiple cluster environments.