parallel-tsp

Project dependencies

Python

Version 3.12

Open MPI

Version 5.0.3

Installation

Get an MPI implementation

While any MPI implementation should work, here are my recommended options.

For macOS, you can install Open MPI using Homebrew:

brew install openmpi

For Linux, you may need to either install Open MPI from source or check your distribution’s repositories. For example, on Ubuntu/Debian, MPICH is readily available:

sudo apt install mpich

For Windows, Microsoft MPI is required. Follow the Microsoft MPI installation guide for instructions.

Install poetry

This project uses Poetry for dependency management. Please refer to the offical docs for installation details.

Install dependencies

# install dependencies
poetry install
# activate the virtual environment 
poetry shell

You're all set! You can now run examples, tests, and other code from this repository.

Running examples

Genetic Algorithm

python examples/run_ga_example.py

Genetic Algorithm with Local Optimisation

python examples/run_optimized_example.py

Genetic Algorithm with MPI Strategy

mpiexec -n 4 python examples/run_ga_mpi_example.py

Running tests

Functional

pytest -m functional

Functional MPI

mpiexec -n 4 python -m pytest -m mpi

Running benchmark

The 8 is an arbitrary value and you can use as many parallel environments as many your MPI implementation detects.

for cores in {1..8}; do echo "Running with $cores cores"; time mpiexec -n $cores python benchmark/hyperparameter_search.py; done

Inspirations and references

Travelling Salesman Problem: Parallel Implementations & Analysis

Optimal Low-Latency Network Topologies for Cluster Performance Enhancement