Computer Network for D15112
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.
|
