QAPLIB - A Quadratic Assignment Problem Library

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


Welcome to the QAPLIB Home Page, the online version of
QAPLIB - A Quadratic Assignment Problem Library
(Journal of Global Optimization 10:391-403, 1997).

We appreciate any comments and contributions to QAPLIB and hope that this site becomes a valuable source for research on the quadratic assignment problem.

The QAPLIB Home Page is accessible since April 1996 and consists of two mirror sites.
[ Site at Technical University Graz, Austria | Site at Technical University of Denmark]


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=20. 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 us at that time. Due to the continuing demand for these instances, and the strong feedback from many researchers, we provided a major update in 1994, which was also accessible through anonymous ftp. In this update we also included many new problem instances, generated by several researchers for their own testing purposes. Moreover, we included a list of current champions, i.e. best known feasible solutions, and best lower bounds.

The update of April 1996 reflects on one hand the big changes in electronic communication. It has become a World Wide Web site, the QAPLIB Home Page. The online version will be updated on a regular basis and also contains most of the currently best known permutations. On the other hand, we feel the update was necessary, due to the increased research activities around the QAP, carried out in the last years. Therefore we also include a short list of dissertations concerning QAP, which were written in the last few years.

We hope that, with your help, the QAPLIB Home Page will be an up-to-date source for the QAP. We plan to put in a more complete bibliography and other items of interest in the future.


Acknowledgments

We thank all colleagues who contributed to QAPLIB over the last years. For the April 1996 update we are particularly grateful to Eranda Cela for pointing out several references, and to Charles Fleurent, Michael Perregaard, Mauricio Resende and Eric Taillard for making their data and solutions available to us.


Contact Addresses

Stefan E. Karisch, IMM, Department of Mathematical Modelling, Technical University of Denmark, Building 321, DK-2800 Lyngby, Denmark; Email: sk@imm.dtu.dk

Franz Rendl, Department of Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria; Email: rendl@opt.math.tu-graz.ac.at


March 1998. Stefan Karisch, sk@imm.dtu.dk