QAPLIB - A Quadratic Assignment Problem Library
R.E. BURKARD, E. ÇELA, S.E. KARISCH and F. RENDL
What's New?
Recent entries in QAPLIB Home Page are marked by
"*". The dates (mm/yy) in the list below indicate when the entry was received for inclusion in QAPLIB.
May 2018:
- Hans Mittelmann reports improvement of nineteen lower bounds utilizing the code BBCPOP by
Naoki Ito, Sunyoung Kim, Masakazu Kojima, Akiko Takeda, and Kim-Chuan Toh.
Sparse doubly-nonnegative relaxations are used for polynomial optimization problems such as the QAP.
For details including full computational results, see here.
November 2017:
- Volodymyr Shylo reports a new record solution for tai100a with the objective of 21044752.
This solution was found with RITSK (Repeated Iterated Tabu Search Kernel) using the multi-processor complex SKIT-4
at the Glushkov's Institute of Cybernetics (Kiev, Ukraine).
6 August 2017:
- The reformulation technique "Non Diagonal Quadratic Convex Reformulation (NDQCR)" by Pörn, Nissfolk, Skjäl, and Westerlund,
recently succeeded in improving the global lower bound for the Tai256c instance to a value of 44095032, which is only
1.48% below the value of the best known solution.
NDQCR is generally created for solving zero-one quadratic programs. The QAP is one of the applications
illustrated in the recent article on NDQCR.
Information about the Tai256c instance is found here.
20 July 2011:
- The parallel RLT1/RLT2/RLT3 branch-and-bound search code written by Amir Roth and Peter Hahn succeeded yesterday in solving for the first time the Tai30b instance of the QAP.
This was done on the Palmetto Supercomputing Cluster at Clemson University,
thanks to the efforts of our colleague Matt Saltzman and the staff of the Cyber Infrastructure Technology Integration Group at Clemson.
The paper related to this new result is available here.
Information about the Tai30b instance is found here.
- Peng, Zhu, Luo and Toh announce significantly improved lower bounds for several large instances of Taixxb using an improved matrix splitting called sum-matrix splitting (SDRMS-SUM). A paper can be found here.
May 2011:
- Axel Nyberg and Tapio Westerlund announce the exact solution of the
only remaining esc instance, esc32b, using an improved version of the
discrete MILP formulation presented earlier. Therefore all esc
instances are now solved to global optimum. The solution to esc32b
turned out to be a confirmation of the best known solution as well.
The solution took about 2 days with Gurobi 4.5.1 with default
parameters on a single PC.
- Matteo Fischetti, Michele Monaci and Domenico Salvagnin at the University of
Padova announce the exact solution, for the first time, of instances esc128
(at present, the largest QAPLIB instance solved to proven optimality) and
esc32h. Their method is based on a MILP branch-and-cut solver built on top of IBM
ILOG Cplex 12.2. Proving optimality for esc32h required about 2 hours on a single
quadcore PC, while the solution of "the big fish" esc128 required just a few
seconds on the same hardware. Instances esc32c, esc32d, and esc64a were solved
as well--all together, their solution required less than half an hour. Instance
tai64c was solved in about 5 hours on the same PC. A full paper is available from
the authors.
Jan 2011:
- Axel Nyberg & Tapio Westerlund at Abo Akademi University in Finland
(www.abo.fi/ose) announce that they have a discrete QAP reformulation
that results in an MILP problem. So far, they have solved the QAPLIB
instances esc32a, esc32c, esc32d, esc64a to optimality as well as the
previously solved tai64c. esc32c took, with the current version of the
model, 9 hours to solve on a single PC running windows 7 when solving
the model with gurobi 3.0 (default settings). esc32d took about 35
hours. The solutions found are the same as the best known solutions
for all these instances. They are still trying to solve other
instances, especially the remaining esc32* instances, however, these
are very difficult. But, they have new improved lower bounds and hope
to be able to solve some more instances to proven optimality. A paper
about the formulation used can be found here.
Jan 2009:
- Zhongzhen Zhang writes that the QAP may be solved efficiently by a
pivoting based algorithm for quadratic programming. Experiments are
conducted on instances of Nug,
Tai, Chr, Had, Rou, Bur, Esc and Tho for n = 12 to 40. Using this
method, multiple optima are found for most problems, including the
famous Nug30, in several seconds
to several minutes. About 80 optimal solutions are presented that have
never been published in the literature.
Download paper here.
Dec 2007:
- Hans Mittleman and Jiming Peng announce the
development of a new semi-definite relaxation-matrix splitting bound:
(SDRMS). The lower bounds for several large instances of Taixxb were
improved significantly, using this new bound. A paper on this subject
is being written.
-Recently, Etienne de Klerk and Renata Sotirov have improved several
bounds on the escxx instances. A very important result is computing the
SDP bound for the QAP instance 'Esc64'. You can find their results
online, in the paper: [DKSo:07].
May 2007:
-After long lasting experiments, Misevicius found a new best-known solution for the
QAP instance 'tai100a'. The new best-known solution is found by using an improved iterated tabu search (IITS)
algorithm. A paper on this subject is in preparation.
Jul 2006:
- Sergio Carvalho, et al. announce a new QAP application, the
Microarray Placement Problem, where one wants to find an arrangement of
the probes (small DNA fragments) on specific locations of a microarray
chip. There are two evaluation criteria: border length and conflict
index (these models are somewhat correlated, i.e. a good layout has
both low border length and low conflict indices). Both models lead to
symmetric QAP instances.
Some problem instances derived from their work are now available at: http://gi.cebitec.uni-bielefeld.de/comet/chiplayout/qap. On the page, there are links to a paper and a poster with more information about their problem.
Sep 2005:
Improved lower bounds:
- Hahn announces a new lower bound for the tai50b. This new bound
(118,875,235) was calculated using the Dual Procedure (DP) as described
in [HaGr:95].
It replaces a much poorer GLB bound (40,296,004). If anyone requires
the calculation of an improved QAP lower bound, please get in touch
with Hahn at petermhahn@gmail.com.
Aug 2005:
Improved best known solutions:
- Misevicius announces a new best-known solution to the tai100a. This new solution was obtained
using the iterated tabu search (ITS) algorithm described in:
[Mise:07].
Mar 2005:
Improved best known solutions:
- Drezner announces a new best-known solution to the tai100a, using a hybrid genetic algorithm. This algorithm is described in:
[Drez:03].
- Misevicius announces a new best-known solution for the tai80a. This
new solution was obtained by using the iterated tabu search (ITS)
algorithm described in: [Mise:07].
Oct 2004:
Improved best known solutions:
- Misevicius announces that, after additional long-lasting experiments,
new record-breaking solutions for the instances 'tai80a' and 'tai100a'
have been found. These new solutions were obtained by using an iterated
tabu search (ITS) algorithm. This algorithm is described in: [Mise:07].
Sept 2004:
QAP Survey article:
- A new survey, "An Analytical Survey for the Quadratic Assignment
Problem," by E.M. Loiola, et al., is available here. It is being
considered for publication by the European Journal of Operational Research. The PDF file is 2.8 MB.
Download: Survey
June 2004:
Global optima:
- GATS is a new hybrid (Genetic Algorithm / Tabu Search) algorithm
based on the concept of the "evolution of populations of populations" [Rodriguez:04].
Our main interest at the University of New Brunswick (Mechanical
Engineering Department / Advanced Computational Research Laboratory) is
to obtain all global optima when solving QAP/DPLP (an extension of QAP)
instances. Running GATS in a high-performance computing (HPC)
environment, a population/convergence factor (P-CF) matrix is
constructed via parameter sweep, which is then used to efficiently
search the instance solution space. During the first stage of our
research and after performing a large number of computational
experiments with 200 QAP and DPLP instances from the QAPLIB, a selected
DPLP data set [BaChCoLau:03], and other difficult instances [DrHaTa:03], we concluded that a remarkable number (74%) of the instances could be efficiently solved using GATS [RoMcBoBh:04]: [http://acrl.cs.unb.ca/research/gats]
New lower bounds:
- Sam Burer and Dieter Vandenbussche announce new bounds obtained for
the following problem instances: esc32a-d,h and tai35a,b. A technical
report that describes the details may be found at: http://www.optimization-online.org/DB_HTML/2004/06/890.html
- Peter Hahn announces an improved bound for the tai30b. It was
calculated using the level-2 Reformulation Linearization Technique of
Hahn and Hightower: [HHJGSR:01]
March 2004:
Optimal solutions:
- Hahn announces the exact solution of the Bur26b-h instances, which
have remained unsolved since 1977. All Bur26 instances are now solved.
These problem instances were relatively easy for a branch-and-bound
algorithm based on the level-1 RLT formulation of Adams and Sherali.
The latest version of this algorithm is described in: [HHJGSR:99].
The algorithm found all the optimum solutions. The bur26c,e,g each have
96 optimum solutions. The bur26 b,d,f,h each have 1536 optimum
solutions. Branch-and-bound enumeration runtimes varied from 7.5
minutes to 27.2 hours on a single cpu of a 360MHz Sun Ultra 10
workstation.
Improved best known solutions:
- Misevicius announces that, after extensive experimentation, a number
of new improved best known solutions for the random instances Tai50a,
Tai80a and Tai100a have been found. All these new solutions were
obtained by using an iterated tabu search (ITS) algorithm. This
algorithm is described in: [Mise:07].
June 2003:
New instances available:
- Palubeckis announces the generation of a new set of QAP instances
containing the provably optimal value of the objective function. Some
computational experience, though rather limited, shows that instances
in this set are not very easy for the heuristics for the QAP. Probably,
these instances could sometimes be used in experiments together with
the instances from the QAPLIB (or even be included into the QAPLIB if
they will appear to be sufficiently strong). The set is available at : http://www.soften.ktu.lt/~gintaras/qproblem.html
Improved best known solutions:
- Misevicius improved the best known solution of Tai60a. This was
unexpected since the previous solution by Taillard was considered
pseudo-optimal. Misevicius also found an improved best known solution
of the Tai80a.
The new solution was obtained by using a modified tabu search
algorithm.
This algorithm is described in: [Mise:03a].
April 2003:
Improved best known solutions:
- Misevicius improved the best known solution of Tai100a.
The new solution was obtained by using an iterated tabu search (ITS) algorithm.
This algorithm is described in:
[Mise:07].
February 2003:
Improved best known solution:
- Misevicius improved the best known solution of Tai80a.
The new solution was obtained by using a modified tabu search algorithm.
This algorithm is described in:
[Mise:03a].
New instances available:
- Taillard and Drezner announce the generation of new QAP instances that are
ill conditioned and therefore difficult for most metaheuristic-based methods.
However, these new instances are shown to be solved relatively easily by
an exact method, since many of them up to size 75 have been exactly solved.
(See [DrHaTa:03].)
These new instances are found respectively at:
http://www.eivd.ch/ina/Collaborateurs/etd/problemes.dir/qap.dir/qap.html and http://business.fullerton.edu/zdrezner/programs.htm
Optimal solutions:
- Peter Hahn solved the Tai25a to optimality using the same code as was
used to solve the Kra30a (see below). The enumeration took 393.5 days
on one 420 MHz cpu of a HPJ5000 workstation. The optimum found is the
already best known solution.
October 2002:
Correction:
- Kurt Anstreicher, Nathan Brixius, Jean-Peirre Goux and Jeff Linderoth announce:
We have discovered that due to a clerical error the optimal value for the
kra32 QAP is misreported in our paper "Solving large quadratic assignment
problems on computational grids," Math. Programming B 91 (2002), 563-588.
The correct optimal value for the problem is 88700. An optimal permutation
(assignment of facilities to locations) attaining this value IS correctly
reported in Table 8 of the paper.
Due to our error in reporting the optimal value, the comments in Section 6
of the paper comparing the kra32 and kra30a QAPs are incorrect. In
particular, the choice of locations removed from the original 4x4x2 grid to
form the kra30a problem DO NOT correspond to the optimal solution over the
entire grid (i.e., the kra32 problem).
We are grateful to Mauricio Resende for bringing this error to our attention.
Improved best known solutions:
- Misevicius improved the best known solution of Tai80a.
The new solution was found by applying a tabu search algorithm described in [Mise:05].
- Misevicius also reports new (best known) solutions for the QAP instances
corresponding to the elaboration of grey frames (known as grey density problems).
Instances of this type are described in (Taillard, E. 1995. Comparison of iterative
searches for the quadratic assignment problem. Location Science 3: 87-105) and
(Taillard, E., L.M. Gambardella. 1997. Adaptive memories for the quadratic
assignment problem. Tech. Report IDSIA-87-97, Lugano, Switzerland) under the name
grey_n1_n2_m, where m is the density of the grey (0<=m<=n=n1xn2), and n1xn2 is
the size of a frame. [The MS DOS/Windows-based program for grey density instances
generation can be downloaded from the location: ftp://pik.ktu.lt/pub/misevi/greydens/]
January 2002:
Optimal solutions:
-Anstreicher, Brixius, Goux and Linderoth
solved Kra30b, Kra32 and Tho30 to optimality (November 2000)
(see also http://www.optimization-online.org/DB_HTML/2000/10/233.html) -
On December 2000 Peter Hahn announced that he had solved Kra30b to
optimality by using the same code as for the solution of Kra30a (see
below).
The computation time needed by Hahn et al. amounted to 182 days
(15,737,136 seconds) on a single cpu HP-3000 workstation, while the
computation time needed to solve Kra30b by Anstreicher et al. would
amount to the equivalent of 2.7 years on a single cpu HP-3000
workstation.
- Nyström solved Ste36b und Ste36c to optimality (27/10/1999).
The author proved the optimality of the former best known values found by using
tabu search approaches.
(see also http://www.async.caltech.edu/~mika/stein.psx)
- Brixius and Anstreicher solved Ste36a to optimality (12/10/2001).
The authors proved the optimality of the former best known value found by Skorin-Kapov by using a
tabu search algorithm.
(see also http://www.biz.uiowa.edu/faculty/anstreicher/wiring.ps)
- Brixius and Anstreicher solved Ste36c to optimality (19/11/2001) -
without knowing that this instance was already solved to optimality by Nyström as mentioned
above.
(Also the authors of QAPLIb did not know about the solution found by Nyström; this is the
reason why Nyström's results was included in QAPLIB only with the update of Jan. 2002.)
The authors proved the optimality of the former best known value found
by Taillard by using a robust tabu search algorithm. The branch and
bound algorithm which led to the optimal solution is the same as the
one used to solved Ste36a described in the reference given above.
- Hahn solved Bur26a to optimality (19.10.2001).
It turned out that the best known solution of Bur26a found by a Grasp
algorithm [LiPaRe:94] is an optimal one.
The optimal solution was obtained by applying the Hahn and Grant bound
[HaGr:95] within the branch and bound algorithm described in [HaHiJoGu:01].
Improved best known solutions:
- Misevicius improved the best known solution of Tho150.
The new solution was found by applying a simulated annealing algorithm described in [Mise:03c].
Test instances:
-The instance Kra32 was included in QAPLIB. This instance was generated
by Anstreicher, Brixius, Goux and Linderoth as a modification of
Kra30a. The authors use the distance matrix of the complete 4 by 4 by 2
grid involved in Kra30a and add to dummy facilities. (November 2000).
For more details see http://www.optimization-online.org/DB_HTML/2000/10/233.html)
June 2000:
Optimal solutions:
-Anstreicher, Brixius, Goux and Linderoth
solved Nug30 to optimality. (19/6/2000)
(see also http://www.mcs.anl.gov/metaneos/nug30)
Codes:
An implementation of the simulated annealing algorithm of [Connolly:90], due to
Taillard
was included in QAPLIB.
An implementation of an ant system approach of [Taillard:98] , due to
Taillard
was included in QAPLIB.
April 2000:
Test instances:
-The instance Nug27 was included in QAPLIB. This instance was generated by
Anstreicher, Brixius, Goux
and Linderoth
by removing the three last facilities from the Nug30 instance. (23/2/2000)
-The instance Nug28 was included in QAPLIB. This instance was generated by
Anstreicher, Brixius, Goux
and Linderoth
by removing the two last facilities from the Nug30 instance. (13/4/2000)
Optimal solutions:
-Anstreicher, Brixius, Goux and Linderoth
solved Nug27 to optimality. (23/2/2000)
(see also http://www.ncsa.uiuc.edu/SCD/Alliance/datalink/0003/QA.Condor.html)
-Anstreicher, Brixius, Goux and Linderoth
solved Nug28 to optimality. (13/4/2000)
(see also http://www.ncsa.uiuc.edu/SCD/Alliance/datalink/0003/QA.Condor.html)
- Hahn, Hightower, Johnson, Guignard-Spielberg and Roucairol [HHJGSR:99] solved
kra30a to optimality. (31/3/2000)
There are 256 optimal solutions of this problem, all of them also found by
Stützle [Stu:99] by iterated local search.
The solution to optimality confirmed that the best known value so far (88900)
is optimal. A solution yielding this objective function value was already found in 1990 by Skorin-Kapov [Skorin:90].
References:
- The survey chapter of Burkard, Çela, Pardalos and Pitsoulis
[BCPP:98] has been included
in the survey section. (August 1998)
March 1998:
Optimal solution:
- A. Brüngger and A. Marzetta [BrMa:97]
proved optimality of the best known solution for Nug25. (3/3/97. Note that 1997 is not a typo!)
Feasible solutions:
- S. Amin
[Amin:98] provided an improved solution for
Tho150. (9/3/98)
Lower bounds:
- S.E. Karisch, E. Çela, J. Clausen, and T. Espersen
[KaCeClEs:98]
improved the lower bounds for the instances Bur26x, Kra30a, and
Tai25a. (3/3/98)
References:
- E. Çela's book [Cela:98] has been included
in the survey section.
December 1997:
Feasible solutions:
- E.D. Taillard and L.M. Gambardella
[TaGa:97] provided an improved solution for
Tho150. (4/12/97)
October 1997:
Optimal solution:
- M. Giovannetti [Giovannetti:97,
Maniezzo:97] proved optimality for Tai25b.
(2/9/97)
Lower bounds:
- V. Kaibel [Kaibel:97,
Kaibel:97a]
improved the lower bounds for the instances Esc32a, Esc32b, Esc32c, Esc32d,
Esc32h. (2/10/97)
References:
- V. Kaibel's PhD thesis on polyhedral combinatorics of the quadratic
assignment problem [Kaibel:97] (2/10/97)
August 1997:
Optimal solution:
- P. Hahn [HaGrHa:96] solved Tai20b to
optimality. (29/7/97)
Feasible solutions:
- T. Stützle [Stuetzle:97] provided
an improved solution for Tai256c. (17/6/97)
- E.D. Taillard and L.M. Gambardella
[TaGa:97] provided an improved
solution for Tai150b. (18/7/97)
Software:
- E.D. Taillard made a Pascal implementation of his robust taboo search
algorithm [Taillard:91] available.
(18/7/97)
June 1997:
V.-D. Cung, T. Mautor, P. Michelon and A. Tavares
[CuMaMiTa:97] provided an improved
solution for Tho150. (The work dates back to December 1996 and includes
the then best solution of Tai256c, too.)
March 1997:
E.G. Talbi, Z. Hafidi and J-M. Geib
[TaHaGe:97] provided improved solutions
for Tai150b and Tai256c.
January 1997:
H. Iriyama [Iriyama:97] found an
improved solution for Tai256c.
December 1996:
Optimal solutions:
- J. Clausen, T. Espersen, S.E. Karisch, M. Perregaard, and S. Tschöke
[CEKPT:96]
solved Nug24, the largest "Nugent type" problem up do date. (26/11/96)
- A. Bruengger, J. Clausen, A. Marzetta and M. Perregaard
[BrClMaPe:96]
provide an optimal solution for Esc32g. (11/12/96)
Lower bounds:
- P. Hahn, T. Grant and N. Hall [HaGrHa:96]
improved the lower bounds for the instances Tai20b, Tai25a, and Tai25b.
References:
- Q. Zhao's PhD thesis on semidefinite programming approaches for the QAP
[Zhao:96]
September 1996:
The revised version of the technical report is available (
postscript of 9/96).
July 1996:
Problem Instances:
- We added "Nugent type" instances of size n={21,22,24,25}.
(04/07/96)
Optimal solutions:
- The largest "Nugent type" problem solved to optimality is Nug22.
(04/07/96)
- A. Bruengger, J. Clausen, A. Marzetta and M. Perregaard
[BrClMaPe:96]
provided optimal solutions for Esc32e, Esc32f, Had18, Had20, Nug21, Nug22,
Rou20, Tai17a, Tai20a.
(04/07/96)
- P. Hahn, T. Grant and N. Hall [HaGrHa:96]
proved optimality for Had16.
(04/07/96)
Feasible solutions:
- T. Ostrowski and V.T. Ruoppila [OsRu:96]
provided an improved solution to Tai256c. (04/07/96)
Fortran Codes:
- The problem generator of Y. Li and P.M. Pardalos
[LiPa:92] can be obtained by sending an E-Mail
to coap@math.ufl.edu and
putting "send 92006" in the body of the mail message. (04/07/96)
April 1996:
New data of this update of QAPLIB compared to the one of
February 1994 are marked by (4/96).
GO BACK TO MAIN
PAGE OF QAPLIB