* Problem solved exactly by lower bound calculation

**Optimumverified 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 Gilmore-Lawler bound from Gilmore (1962); RRD95 is the interior-point bound from Resende et al. (1995); HG98 is the RLT-1 dual ascent bound from Hahn and Grant (1998); KCCEB99 is the dual-based bound from Karisch et al. (1999); AB01 is the quadratic programming bound from Anstreicher and Brixius (2001); RRRP02 is the RLT-2 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 lift-and-project SDP bound from Burer and Vandenbussche (2006); HH01 is the Hahn-Hightower RLT-2 dual ascent bound from Adams et al. (2007); and HZ07 is the Hahn-Zhu RLT-3 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 RLT-2 lower bound described in Adams, et al. (2007) and in Ramakrishnan et al. (2002).
Also, HG98 is a dual ascent procedure that underestimates the interior-point 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 level-2 reformulation-linearization technique bound for the quadratic assignment problem, European Journal of Operational Research 180, 983-996.  First available as Working Paper 01-04, 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, 341-357.

 

Burer, S. and Vandenbussche, D. (2006) “Solving Lift-and-project Relaxations of Binary Integer Programs,” SIAM Journal on Optimization, 16, 726-750.  First available in 2004 on http://www.optimization-online.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 max-Cut and equipartition,Ó Mathematical Programming 105, 451-469.

 

Gilmore, P.C., 1962, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10, 305-313.

 

Hahn, P.M., and T.L. Grant, 1998, Lower bounds for the quadratic assignment problem based upon a dual formulation, Operations Research 46, 912-922.

 

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, 351-403.

 

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, 297-303.

 

Rendl, F., and R. Sotirov, (2007) Bounds for the quadratic assignment problem using the bundle method, Mathematical Programming 109, 505-524. 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,
781-791.

 

Zhu, Y-R., ÒRecent Advances and Challenges in Quadratic Assignment and Related Problems,Ó Ph.D. Dissertation, University of Pennsylvania, 2007.