Lower Bounds for the Quadratic Assignment Problem

Y. Li, P.M. Pardalos, K.G. Ramakrishnan, and M.G.C. Resende

Annals of Operations Research, vol. 50, pp. 387-411, 1994


We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem.  We provide evidence of the difficulty of improving the Gilmore-Lawler Bound and develop new bounds by means of optimal reduction schemes.  Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 27 September 2010

Copyright Notice