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 q uadratic assignment problem (QAP), incorporating the lower bound based on variance reduction of Li, Pardalos, Ramakrishnan, and Resende (199 4), 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 o f QAP test problems are reported. The branch-and-bound algorithm using the new lower bounds is compared with the same algorithm utilizing th e commonly applied Gilmore-Lawler lower bound. Both implementations us e 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 di mensions 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 th e branch-and-bound tree than the same algorithm using the Gilmore-Lawl er lower bound.