iSGTW - International Science Grid This Week
iSGTW - International Science Grid This Week
Null

Home > iSGTW 30 January 2008 > iSGTW Feature - Traveling salesman meets distributed computing

 

Feature - Traveling salesman meets distributed computing


The traveling salesman problem (TSP) is solved when the salesman travels through each of “n” cities while covering the least total distance. This shortest route is called a Hamiltonian circuit; however, there is no known general method for finding the TSP solution.
Image courtesy of Wolfram Mathworld

The traveling salesman problem (TSP) is a classic combinatorial problem: given a set of cities, what is the path that visits each city once and only once, while covering the minimum distance?

For a small set of cities, the solution is trivial and can be discovered by simple inspection; however, the solution for even a moderate number of cities is out of reach for most home computers. For example, to exhaustively check all possible paths for a 48 city instance—assuming you could check one million paths a second—would take approximately 1047 years.    

Despite all the research, there is still no known general solution to the TSP.

Who cares about traveling salesmen?

Do we really need to know how to get a traveling salesman to our door in the shortest time? No, but generic forms of the TSP have been used in laying out circuit boards, cutting raw materials, clustering data arrays, analyzing crystal structures, scheduling and much more.

Distributed salesmen

The first goal of the TSP project is to do an exhaustive search of a 48 city TSP. Once the optimal paths are known, we will test the various search algorithms for their ability to find these optimal paths.

The next step will be to see if a combination of search algorithms and brute force tactics can produce an optimal result. Then it will be time to stress test any theories that come from this work by searching some really big TSPs.   

In the beginning

The TSP project started out as a proof of concept. I just wanted to see if I could do it. I thought I would just put up this little project and have a few friends attach to it.

The TSP project’s first task is to calculate the optimum solution to the TSP across 48 cities in the U.S. New solutions are constantly being computed using BOINC-powered volunteer distributed computing.
Images courtesy of TSP

Somehow word got out, and before I knew it, a group of alpha testers were in the forums providing encouragement. According to allprojectstats.com I have 1400 hosts and 600 users representing 50 countries: it’s all thanks to the BOINC community. 

Why TSP runs: a few thank yous

There are very few “killer apps” in this world and BOINC qualifies in every aspect.

Some of the most smart, friendly, unassuming and patient folks from around the world are always ready to help. The BOINC community provides help with every aspect of the project: code development, server configuration, advice on end user expectations, credit granting schemes, client setup, application development... 

I may have written the software, but it’s the BOINC community that keeps this project going. People have volunteered their time to build applications for different platforms, or to build optimized applications.  All the graphics on the site were courtesy of a BOINC community member volunteering their time. 

-  Markus Weltin, TSP director

 

Tags:



Null
 iSGTW 22 December 2010

Feature – Army of Women allies with CaBIG for online longitudinal studies

Special Announcement - iSGTW on Holiday

Video of the Week - Learn about LiDAR

 Announcements

NeHC launches social media

PRACE announces third Tier-0 machine

iRODS 2011 User Group Meeting

Jobs in distributed computing

 Subscribe

Enter your email address to subscribe to iSGTW.

Unsubscribe

 iSGTW Blog Watch

Keep up with the grid’s blogosphere

 Mark your calendar

December 2010

13-18, AGU Fall Meeting

14-16, UCC 2010

17, ICETI 2011 and ICSIT 2011

24, Abstract Submission deadline, EGI User Forum

 

January 2011

11, HPCS 2011 Submission Deadline

11, SPCloud 2011

22, ALENEX11

30 Jan – 3 Feb, ESCC/Internet2

 

February 2011

1 - 4, GlobusWorld '11

2, Lift 11

15 - 16, Cloudscape III


More calendar items . . .

 

FooterINFSOMEuropean CommissionDepartment of EnergyNational¬†Science¬†Foundation RSSHeadlines | Site Map