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

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.