QAPLIB - A Quadratic Assignment Problem Library

R.E. BURKARD, E. ÇELA, S.E. KARISCH and F. RENDL


Welcome to the QAPLIB Home Page, the online version of 
QAPLIB - A Quadratic Assignment Problem Library  
by R.E. Burkard, S.E. Karisch and F. Rendl,

(Journal of Global Optimization 10:391-403, 1997.)

We appreciate any comments and contributions to QAPLIB and hope that this site continues to be a valuable source for research on the quadratic assignment problem.
QAPLIB originated at the Graz University of Technology, where the version from February 2002 is still available at Site at Graz University of Technology, Austria

Since August 2002, the QAPLIB page has been maintained at the University of Pennsylvania, School of Engineering and Applied Science, by Peter Hahn,
Email hahn@seas.upenn.edu  
Since July 2011, the QAPLIB has a mirror site at Ecole Polytechnique de Montreal, by Miguel Anjos,
Email miguel-f.anjos@polymtl.ca  


Contents

[ Postscript (9/96) | Compressed Data | Compressed Solutions ]

Introduction

The Quadratic Assignment Problem (QAP) has remained one of the great challenges in combinatorial optimization. It is still considered a computationally nontrivial task to solve modest size problems, say of size n=25. The QAPLIB was first published in 1991, in order to provide a unified testbed for QAP, accessible to the scientific community. It consisted of virtually all QAP instances that were accessible to the authors at that time. Due to the continuing demand for these instances, and the strong feedback from many researchers, a major update was provided by Burkard, Karisch and Rendl in 1994. This update was also accessible through anonymous ftp. This update included many new problem instances, generated by several researchers for their own testing purposes. Moreover, a list of current champions, i.e. best known feasible solutions, and best lower bounds was included.

The update of April 1996 reflected on one hand the big changes in electronic communication. QAPLIB became a World Wide Web site, the QAPLIB Home Page. On the other hand, the update was necessary, due to the increased research activities around the QAP. A short list of at-that-time-recent dissertations concerning QAP, was included.

The update of June 2000 reflects the progress made on the QAP especially on solving new test instances and test instances which were previously not solved to optimality. It includes an updated list of people working on the QAP and an updated list of surveys and dissertations on the QAP.

The update of January 2002 reflects the progress made more recently on the QAP. The emphasis relies on the optimal solution of test instances which were previously not solved to optimality. The optimal solutions were obtained by using new bounding techniques and new branch and bound schemes generally implemented in very powerful parallel computation environments. This update also includes new test instances and some improvements on the best known solutions of existing test instances. The list of people working on the QAP as well the list of references have also been updated.

The web site will be updated on a regular basis and we hope that, with your help, the QAPLIB Home Page will be an up-to-date source for the QAP. We appreciate any hints on new and better solutions to existing instances or  new test instances form QAPLIB, as well as any hints on recent literature pointers on the QAP.


Acknowledgments

The QAPLIB home page was created by Stefan Karisch who maintained it until 1997. From 1997 to July 2002 QAPLIB was maintained by Eranda Çela. We thank all colleagues who contributed to QAPLIB over the years. For the April 1996 update we are particularly grateful to Charles Fleurent, Michael Perregaard, Mauricio Resende and Eric Taillard for making their data and solutions available to us. For the updates of June 2000 and January 2002 we would like to particularly thank Kurt Anstreicher, Nathan Brixius, Jean-Pierre Goux, Peter Hahn and Jeffrey Linderoth for providing us with their data and their solutions.

This material is based upon work supported by the National Science Foundation under Grant No. CMMI 0400155.


Contact Information

Please send new results, references, and other updates to one of us:

Peter Hahn, Electrical and Systems Engineering Dept., University of Pennsylvania, 200 S. 33rd Street, Philadelphia, PA 19104, USA;
Email hahn@seas.upenn.edu  

Miguel Anjos, Department of Mathematics and Industrial Engineering, Ecole Polytechnique de Montreal, 2900 Boul. Edouard-Montpetit, Montreal, QC H3C 3A7, Canada;
Email miguel-f.anjos@polymtl.ca  


August 2011 - Peter Hahn (hahn@seas.upenn.edu) and Miguel F. Anjos (miguel-f.anjos@polymtl.ca)