A High-Performance C++ Toolkit that finds optimal tours for classic Travelling Salesman Problem (TSP) instances.
The project contains parallelized Branch-And-Bound (B&B) implementations,
tested on Grid5000's multi-core and multi-node architectures, as well as parallelized implementations of Concorde TSP Solver.
This toolkit aims to find exact solutions to tsplib TSPs for an undirected graph with symmetric edge costs in three ways:
- Parallelizing Concorde on a multi-node architecture
- Implementing an OpenMP suitable Branch and Bound approach for multi-core architectures
- Swapping the default single-threaded LP solver that Concorde uses (QSOPT) with the multi-threaded CPLEX
- Benchmark and record solving times of different implementations in various scenarios
- BaseRec.cpp – Base recursive implementation of Branch and Bound algorithm
- ImprovedRec.cpp – Implemented Bitmasking and a more suitable lower bound
- BaseOpenMP.cpp – Achieved multiple core parallelization via OpenMP
- run_parallel.sh – Parralelizes Concorde on multiple available nodes with different seeds and then lists each node's performance time
- run_parallel_best.sh – Also fires up multiple Concorde runs, but frees resources immediately after one node finishes (the fastest one)
| Layer | Technology / Language |
|---|---|
| Core Algorithm | C++ |
| External TSP Solver | Concorde |
| LP Solver | QSOPT, CPLEX |
| Parallel Execution | Bash, SSH, OpenMP |
| Problem Dataset | TSPLIB (*.tsp) |
| Computational Testbed | Grid5000 |
B.B.Map.TSP.Showcase.mp4
For detailed test run results, visualizations, and in-depth information about the problem and implemented solutions, please visit:
