The quadratic assignment problem (\QAP) is arguably one of the hardest of the NP-hard discrete optimization problems. Problems of dimension greater than 20 are considered to be large scale. Current successful solution techniques depend on branch and bound methods. However, it is difficult to get \emph{strong and inexpensive} bounds. In this paper we introduce a new semidefinite programming (\SDP) relaxation for generating lower bounds for the \QAP. The bound exploits the matrix structure of \QAP and uses $O(n^2)$ variables, a much smaller dimension than other current \SDP relaxations, and the same order of dimension as the original \QAP. We compare this method with several other computationally inexpensive bounds such as the convex quadratic programming relaxation (\QPB). We find that our method provides stronger bounds on average and is adaptable for branch and bound methods.
Citation
CORR 06-22, Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada, September, 2006