-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].
- 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].
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]
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].
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].
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.
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/]
- 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)
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.
-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)
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.
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)
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)
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]
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)