EDITOR'S NOTE: In late February, researchers at the University of Iowa and Argonne National Laboratory sent out email to colleagues to let them know that a large quadratic assignment problem (QAP) had been solved to provable optimality. This email announcement is provided below in its entirety.

The QAP belongs to a larger class of problems known as Combinatorial Optimization Problems. Some readers might not be familiar with Combinatorial Optimization Problems and the challenges inherent in solving them. The email offers readers a glimpse of the long-standing issues facing researchers and the collaborative computational work being pursued to solve them.

The research team used an Alliance computational resource called Condor to compute their solutions. If you are interested in obtaining a start-up allocation on the Condor system for your research, please complete the online request form or submit a request to the Alliance Allocation office. The Iowa/Argonne team's request for time through the Alliance is pending. The Condor development team works at the University of Wisconsin under the direction of Miron Livny.

Location Theory Gives Rise to QAP Problem

The quadratic assignment problem arises as a standard problem in location theory. Researchers are given a set of n locations and n facilities, and told to assign each facility to a location. To measure the cost of each possible assignment -- there are n! of them! -- they multiply the prescribed flow between each pair of facilities by the distance between their assigned locations, and sum over all the pairs. The goal is to find the assignment that minimizes this cost.

Theoretically QAP is NP-Hard and, from a practical standpoint, even relatively small problems (n = 25) are extremely difficult to solve to optimality. Several problems with n = 30 have been open for as long as 30 years! To learn more about the quadratic assignment problem, see http://www.mcs.anl.gov/otc/Guide/CaseStudies/qap/.

email Announcement

 Subject: solution of nug27 QAP
 Date: Wed, 23 Feb 2000 12:44:28 -0600

 Dear colleagues:
 
 We are pleased to announce the exact solution of the nug27 quadratic
 assignment problem (QAP). This problem was derived from the well-known
 nug30 problem (available from QAPLIB) using the distance matrix 
 from a 3 by 9 grid, and the flow matrix from nug30 with the last 3 
 facilities deleted. Refer to the University of Iowa website for more 
 details about the problem data. This, is to our knowlege, the largest 
 instance from the nugxx series ever provably solved to optimality.
 
 The problem was solved using a branch-and-bound algorithm utilizing the QP
 bounds described in "A new bound for the quadratic assignment problem
 based on convex quadratic programming," by K.M. Anstreicher and N.W. Brixius.
 The algorithm was implemented using the Master-Worker (MW) distributed 
 processing system developed as a joint collaboration between researchers 
 at the University of Wisconsin and Argonne National Labs, as part of the 
 MetaNEOS project. 
 
 The computation was performed on a pool of workstations using the Condor
 high-throughput computing system at the University of Wisconsin in an "up"
 computation wall-time of approximately 24 hours. During this time the
 number of active worker machines averaged 136 and peaked at 238. The
 equivalent computation time on a single HP-C3000 workstation would be
 approximately 126 days.  The robust nature of the Condor/MW
 processing systems allows the program to recover from system
 failures as well as allowing the researchers to stop the computation at 
 any point, modify runtime parameters, and continue the computation where
 it left off.   The graph below shows the number of processors used
 by the code during the course of the computation.

 Click here for the PDF version of the graph.

 A permutation with an objective value of 5234 was found by the simulated 
 annealing code of E. Taillard. The branch-and-bound computation was 
 initialized with an incumbent objective value of 5236, and required 
 513,160,139 nodes. The B&B process verified that 5234 is the optimal 
 value for the problem, and found the following permutation with this value:
 
 23 18 3 1 27 17 5 12 7 15 4 26 8 19 20 2 24 21 14 10 9 13 22 25 6 16 11
 
 The same code has also solved the nug25 problem to optimality (nug25 was
 first solved by Bruengger and Marzetta, and has also been solved by Hahn
 and co-workers). Nug25 was solved using 80,430,341 nodes in a wall time of
 6.7 hours, with an average of 94 active workers. The equivalent computation
 time on a single HP-C3000 workstation would be approximately 13 days.
 
 Full details of the branch-and-bound code, and implementation using the MW
 system, will be given in papers under preparation.
 

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

Acknowledgements

Support for this research from the National Science Foundation is gratefully acknowledged under grant numbers CDA-9726385 and CDA-9623632.