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 becomes a valuable source for research on the quadratic
assignment problem.
The QAPLIB Home Page is accessible since April 1996 at [Site
at Graz University of Technology, Austria]
There is also a mirror site of the old version of QAPLIB (March 1998)
[Site
at Technical University of Denmark].
Currently this site is not being updated.
Contents
Links
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 last update of March 2000 aims at reflecting the progress made recently 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.
It also inlcudes a link to QAPNet - which aims at becoming an
information medium on the quadratic assignment problems.
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
We thank all colleagues who contributed to QAPLIB over the last 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 update of April 2000 we would like to thank Kurt Anstreicher, Nathan Brixius,
Jean-Pierre Goux, Peter Hahn and Jeffrey Linderoth for letting us now their data and
their solutions.
Contact Addresses
Eranda Çela, Institute of Mathematics, Graz University of Technology, Steyrergasse
30, 8010 Graz, Austria; Email
cela@opt.math.tu-graz.ac.at
Stefan E. Karisch, Carmen Systems AB, Odinsgatan 9, S-41103, Goeteborg, Sweden. Email: Stefan.Karisch@carmen.se