This repository contains work developed in the Parallel and Distributed Computing masters course at IST.
More specifically, it contains three (one sequential and two parallel) implementations of the Travelling Salesman Problem using the Branch and Bound algorithm.
Regarding the parallel implementations, one was done using OpenMP and the other using MPI (Message Passing Interface).
Grade: 18/20.
| Author | Github |
|---|---|
| Leonor Barreiros | https://github.com/leonormbarreiros |
| Catarina Bento | https://github.com/catarinab |
| João Pereira | https://github.com/joaomhmpereira |
All implementations have their own directory and each already include a Makefile to compile the program.
Directories pub-instances and output contain the available tests (input files) and expected outputs respectively.
After compiling, use the following commands to run the programs:
- Serial
./tsp <path-to-input-file> <max-cost>
- OpenMP
./tsp-omp <path-to-input-file> <max-cost>
- MPI
mpirun -n <number-of-processes> tsp-mpi <path-to-input-file> <max-cost>