Paper Info
Title
Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem
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.
Year
DOI
Venue
1997
10.1137/S1052623494273393
SIAM Journal on Optimization
Keywords
Field
DocType
combinatorial optimization,quadratic assignment problem,branch-and-bound,GRASP,computer implementation,data structures,hashing function,hash table,lower bound,test problems
Data structure,Discrete mathematics,Branch and bound,Mathematical optimization,Upper and lower bounds,Quadratic assignment problem,Permutation,Algorithm,Combinatorial optimization,Greedy randomized adaptive search procedure,Variance reduction,Mathematics
Journal
Volume
Issue
ISSN
7
1
1052-6234
Citations 
PageRank 
References 
15
1.47
4
Authors
4
Name
Order
Citations
PageRank
Panos M. Pardalos169898.99
K. G. Ramakrishnan258798.53
Mauricio G. C. Resende33729336.98
Yong Li417941.58