Travelling salesman problem in Open MP

General OpenMP discussion
Post Reply
Oldboy
Posts: 28
Joined: Wed Oct 31, 2012 2:39 am

Travelling salesman problem in Open MP

Post by Oldboy »

I have found this link:
https://github.com/abhishek510/tsp_openmp

Something is wrong as the speedup is very small from 1 to 4 threads and none at all at 16 threads.

MarkB
Posts: 802
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Travelling salesman problem in Open MP

Post by MarkB »

This implementation doesn't attempt to do any load balancing of the parallel branch-and-bound algorithm. Using nested tasks might be a better way to go.

Oldboy
Posts: 28
Joined: Wed Oct 31, 2012 2:39 am

Re: Travelling salesman problem in Open MP

Post by Oldboy »

Thank you Mark!

This Boruvka version of TSP works better:
https://github.com/dimitris21gr/Boruvka ... MP_boruvka

A "small" misstake must be corrected parralel -> parallel in the c-code.

Post Reply