Instance 
Optimum 
GLB62 
RRD95 
HG98 
KCCEB99 
AB01 
RRRP02 
RS03 
R04 
BV04 
HH01 
HZ07 
Had16 
3720 
3358 

3558 
3553 
3595 

3699 
3720** 
3672 
3720* 
3719.1** 
Had18 
5358 
4776 

5083 
5078 
5143 

5317 
5356 
5299 
5358* 
5357.0** 
Had20 
6922 
6166 

6571 
6567 
6677 

6885 
6920 
6811 
6922* 
6920.0 
Kra30a 
88900 
68360 
76003 
75853 
75566 
68572 

77647 

86678 
86247 

Kra30b 
91420 
69065 
76752 
76562 
76235 
69021 

81156 

87699 
87107 

Nug12 
578 
493 
523 
523 
521 
498 
578* 
557 
567 
568 
578* 
577.2** 
Nug15 
1150 
963 
1041 
1039 
1033 
1001 

1122 
1138 
1141 
1150* 
1149.1** 
Nug18 
1930 










1930* 
Nug20 
2570 
2057 
2182 
2179 
2173 
2290 

2451 
2494 
2506 
2508 
2568.1** 
Nug22 
3596 









3511 
3594.04** 
Nug30 
6124 
4539 
4805 
4793 
4785 
5365 

5803 

5934 
5770 

Rou15 
354210 
298548 
324869 
323943 
323589 
303777 

333287 
348838 
350207 
354210* 
354210* 
Rou20 
725520 
559948 
643346 
642058 
641425 
607822 

663833 
691124 
695123 
699390 
725314.4 
Tai20a 
703482 
580674 

617206 
616644 
585139 

637300 

671685 
675870 
703482* 
Tai25a 
1167256 
962417 

1006749 
1005978 
983456 

1041337 

1112862 
1091653 

Tai30a 
1818146 
1504688 

1566309 
1565313 
1518059 

1652186 

1706875 
1686290 

Tho30 
149936 
90578 
100784 
99995 
99855 
124684 

136059 

142814 
136708 

* Problem solved exactly by lower bound calculation **Optimum
verified by bound calculation
Table 1 – Genesis of Lower Bounds.
Table 1 presents a comparison of lower bounds for a select group of QAPLIB instances. In the Table, GLB62 is the GilmoreLawler bound from Gilmore (1962); RRD95 is the interiorpoint bound from Resende et al. (1995); HG98 is the RLT1 dual ascent bound from Hahn and Grant (1998); KCCEB99 is the dualbased bound from Karisch et al. (1999); AB01 is the quadratic programming bound from Anstreicher and Brixius (2001); RRRP02 is the RLT2 interior point bound from Ramakrishnan et al. (2002); RS03 is the SDP bound from Rendl and Sotirov (2003); R04 is the SDP bound from Roupin (2004); BV04 is the liftandproject SDP bound from Burer and Vandenbussche (2006); HH01 is the HahnHightower RLT2 dual ascent bound from Adams et al. (2007); and HZ07 is the HahnZhu RLT3 bound from Zhu (2007). The best lower bounds are in the shaded cells of the table. Lower bounds are listed in the Table in order of date they were published, with the exception of HH01. The HH01 bound was first published in 2001, but the HH01 bound calculations in Table 1 were recently calculated and thus were placed just before the rightmost column. It should be noted that HH01 is a dual ascent procedure that underestimates the RLT2 lower bound described in Adams, et al. (2007) and in Ramakrishnan et al. (2002). Also, HG98 is a dual ascent procedure that underestimates the interiorpoint bound from Resende et al. (2002).
The Rendl and Sotirov bound is also found in Fischer, I. et al. (2006). In an as yet unfinished technical report, Povh and Rendl (2006) point out that the strongest relaxation (R3) from Rendl and Sotirov (2003) and the relaxation from Burer and Vandenbussche (2004) are actually the same. The differing lower bound values in the two papers are due to the fact that Rendl and Sotirov use the bundle method, which gives only underestimates of the true bound, while Burer and Vandenbussche are able to compute this bound more accurately.
Adams, W.P., M. Guignard, P.M. Hahn, and W.L.
Hightower, 2007, A level2 reformulationlinearization technique bound for the
quadratic assignment problem, European Journal of Operational Research 180,
983996. First available as
Working Paper 0104, Systems Engineering Department, University of
Pennsylvania, 2001 (Authors: P.M. Hahn, W.L. Hightower, T.A. Johnson, M.
Guignard, and C. Roucairol).
Anstreicher, K.M., and N.W. Brixius, 2001, A new bound
for the quadratic assignment problem based on convex quadratic programming, Mathematical
Programming 89, 341357.
Burer, S. and Vandenbussche,
D. (2006) "Solving Liftandproject Relaxations of Binary Integer
Programs," SIAM Journal on Optimization, 16, 726750. First
available in 2004 on http://www.optimizationonline.org/DB_HTML/2004/06/890.html.
Fischer, I., Gruber, G., Rendl, F. and Sotirov, R.
(2006) ÒComputational experience with a bundle approach for semidefinite
cutting plane relaxations of maxCut and equipartition,Ó Mathematical
Programming 105, 451469.
Gilmore, P.C., 1962, Optimal and suboptimal algorithms
for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10,
305313.
Hahn, P.M., and T.L. Grant, 1998, Lower bounds for the
quadratic assignment problem based upon a dual formulation, Operations
Research 46, 912922.
Karisch, S.E., E. ‚ela, J. Clausen, and T. Espersen,
1999, A dual framework for lower bounds of the quadratic assignment problem
based on linearization, Computing 63, 351403.
Povh, J and Rendl, F., (2006) ÒCopositive and
Semidefinite Relaxations of the Quadratic Assignment Problem,Ó unfinished Technical
Report, Department of Mathematics, University of Klagenfurt.
Ramakrishnan, K.G., M.G.C. Resende, B. Ramachandran,
and J.F. Pekny, 2002, Tight QAP bounds via linear programming, in: Pardalos,
P.M., A. Migdalas, and R.E. Burkard (Eds.), Combinatorial and Global
Optimization, World Scientific
Publishing, Singapore, 297303.
Rendl, F., and R. Sotirov, (2007) Bounds for the
quadratic assignment problem using the bundle method, Mathematical
Programming 109, 505524. First available in 2003 as a Technical
Report, Department of Mathematics, University of Klagenfurt.
Resende, M.G.C., K.G. Ramakrishnan, and Z. Drezner,
1995, Computing lower bounds for the quadratic assignment problem with an
interior point algorithm for linear programming, Operations Research 43,
781791.
Zhu, YR., ÒRecent Advances and Challenges in
Quadratic Assignment and Related Problems,Ó Ph.D. Dissertation, University of
Pennsylvania, 2007.