Implementation of a Variance Reduction Based Lower Bound in a Branch and Bound Algorithm for the Quadratic Assignment Problem

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

SIAM Journal on Optimization, vol. 7, pp. 280-294, 1997


The efficient implementation of a branch and bound algorithm for the quadratic assignment problem (QAP), incorporating the lower bound, based on variance reduction, of Li, Pardalos, Ramakrishnan, and Resende (1994), is presented.  A new data structure for efficient implementation of branch and bound algorithms for the QAP is introduced.  Computational experiments with the branch and bound algorithm on different classes of QAP test problems are reported.  The branch and bound algorithm using the new lower bounds is compared with the same algorithm utilizing the commonly applied Gilmore-Lawler lower bound.  Both implementations use a greedy randomized adaptive search procedure for obtaining initial upper bounds.  The algorithms report all optimal permutations.  Optimal solutions for previously unsolved instances from the literature, of dimensions N=16 and N=20, have been found with the new algorithm.  In addition, the new algorithm has been tested on a class of large data variance problems, requiring the examination of much fewer nodes of the branch and bound tree than the same algorithm using the Gilmore-Lawler lower bound.

PostScript file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice