The solution of the 15,112-city traveling salesman problem
was accomplished in several phases in 2000/2001, and used a total of 22.6
years of computer time, adjusted to a 500 MHz, EV6 Alpha processor.
The
initial tour-finding and cutting-plane phases were run on a cluster of
44 Compaq ES40 Alphaservers at Rice Univerity.
The final branching phase of the computation
used additional Compaq DS20, XP1000, and AMD workstations at Rice and a network of Intel based workstations at Princeton University.
A summary of the computers that were used can be found at CPU Network.
The parallel computation was carried out in a master-worker environment, using NSF sockets to communicate between processors. The master process was run on a single node in the Compaq-Rice ES40 cluster, and the worker processes were run on the ES40+DS20+XP10000 and AMD clusters at Rice and the Intel network at Princeton. The worker processes consisted of running the cutting-plane algorithm on sub-problems in the branch-and-bound tree, as well as carrying out branching steps to create new sub-problems. The master process maintained the branch-and-bound search tree and delivered tasks to the workers. The computation also included a cluster of 3 AlphaServer 4100s at Rice (each with 4 processors) that worked as a cut-pool server for the Rice machines (accumulating cutting planes that were found by the workers and distributing these when needed in the solution of other sub-problems), and a single 1,000 MHz Intel Pentium 3 running as a cut-pool server for the Princeton machines. A map of the computing network is given below.
A summary of the computation can be found on the statistics page.
We would like to thank Compaq and AMD for the research relationships that allowed us to obtain the computing clusters at Rice University.