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 (dd/mm/yy) in the list below show when the entry was received for inclusion in QAPLIB.



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:01].

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
February 2002. Eranda Çela, cela@opt.math.tu-graz.ac.at