P.M. Pardalos, K.G. Ramakrishnan, M.G.C. Resende, and Y. Li
SIAM Journal on Optimization, vol. 7, pp. 280-294, 1997
ABSTRACT
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.
Go back
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002