Dear colleagues:

We are pleased to announce the exact solution of the "nug30" Quadratic Assignment Problem (QAP). This problem was first posed in the paper C.E. Nugent, T.E. Vollman, and J. Ruml, "An experimental comparison of techniques for the assignment of facilities to locations," Operations Research 16 (1968) pp. 150-173, and has long been considered an outstanding open "challenge problem" in the optimization literature. The problem data is available from QAPLIB (http://www.opt.math.tu-graz.ac.at/qaplib/).

The problem was solved using the branch-and-bound algorithm described in the paper "Solving quadratic assignment problems using convex quadratic programming relaxations," N.W. Brixius and K.M. Anstreicher, available at http://www.biz.uiowa.edu/faculty/anstreicher/qapqp2.ps. It was implemented using the Master-Worker (MW) distributed processing system developed in the metaNEOS project and described in the paper "An enabling framework for master-worker computing applications on the computational grid," J.-P. Goux, S. Kulkarni, J. Linderoth, and M. Yoder, available from http://www.mcs.anl.gov/metaneos/papers/mw2.ps.

The computation was performed on a dynamic grid of workstations, massively parallel processors, and other CPUs using the Condor high-throughput computing system developed at the University of Wisconsin, together with tools from the Globus toolkit. The total wall-clock time was approximately 6.9 days. The number of worker machines averaged approximately 650, and peaked at 1009. Machines from the following institutions participated in the computation (listed in order of CPU seconds contributed):

• University of Wisconsin
• Argonne National Laboratory
• Georgia Institute of Technology Interactive High Performance Computing Laboratory
• National Center for Supercomputing Applications (NCSA)
• Italian Istituto Nazionale di Fisica Nucleare (INFN)
• Albuquerque High Performance Computing Center
• Northwestern University
• Columbia University

A total of 3.46E8 CPU seconds was expended by worker machines. The equivalent computation time on a single HP-C3000 workstation would be approximately 6.9 years.

According to QAPLIB a permutation with an objective value of 6124 was first obtained by J. Skorin-Kapov, see
J. Skorin-Kapov, "Tabu search applied to the quadratic assignment problem," ORSA J. Computing 2 (1990), pp. 33-45.

The branch-and-bound computation was initialized with an incumbent objective value of 6126, and required 11,892,208,412 nodes. The B&B process verified that 6124 is the optimal value for the problem, and found the following permutation with this value:

14,5,28,24,1,3,16,15,10,9,21,2,4,29,25,22,13,26,17,30,6,20,19,8,18,7,27,12,11,23

Full details of the distributed branch-and-bound implementation using the MW system will be given in a paper under preparation.

Further information can be found at the following URLs:

We are extremely grateful to Steve Wright of Argonne National Lab, and Miron Livny of the University of Wisconsin, for their ongoing support of this research.

Kurt Anstreicher,	University of Iowa
Nathan Brixius,	University of Iowa
Jean-Pierre Goux,	Northwestern University and Argonne National Lab
Jeff Linderoth,	Argonne National Lab