In this project, we explored the Travelling Salesman Problem (TSP), focusing on subtour elimination constraints and variations of the problem. It was my first time using STORM, the high-performance computing (HPC) cluster at Lancaster University. STORM allowed us to run parallelised instances of the problem, enabling the collection of extensive data for comparison and visualisation.
Key Focus Areas
Formulations Investigated:
Dantzig-Fulkerson-Johnson (DFJ): Utilises subtour elimination constraints to ensure solutions are valid Hamiltonian cycles. A dynamic version was implemented to improve scalability by adding constraints iteratively.
Time-Stage (TS): Introduces a time-indexed model to improve constraint handling and solve time, though at the cost of increased complexity.
Variants Examined:
Clustered TSP: Cities were grouped into clusters, and solutions required visiting all cities in a cluster before moving to the next. This variation is relevant in fields like warehouse routing and production planning.
Non-Obvious Applications:
A fascinating extension was the application of TSP to DNA sequence reconstruction, treating DNA fragments as cities and overlaps as edge weights. This allowed the assembly of sequences by minimising superstring length.
Results and Insights
Performance Comparisons: Using STORM, we analysed computational performance across formulations on synthetic datasets and TSPLIB benchmarks. The dynamic DFJ approach significantly reduced memory usage and computation time for larger instances while maintaining accuracy.
Visualisation: Plots generated from parallelised computations highlighted the trade-offs in efficiency and scalability between formulations.
Key Outcomes: The dynamic DFJ formulation stood out for its practical applicability to large-scale problems, with fewer subtour elimination calls and faster solving times compared to the static DFJ and TS formulations.
This project was a valuable introduction to both HPC tools and the complexities of TSP variants, showcasing how computational resources like STORM enable efficient exploration of intricate optimisation problems.