- A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem Yichuan Ding (y7dingmath.uwaterloo.ca) Henry Wolkowicz (hwolkowiczuwaterloo.ca) Abstract: 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. Keywords: Quadratic assignment problem, semidefinite programming Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Combinatorial Optimization Category 3: Applications -- OR and Management Sciences Citation: CORR 06-22, Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada, September, 2006 Download: [Postscript][PDF]Entry Submitted: 10/27/2006Entry Accepted: 10/27/2006Entry Last Modified: 04/19/2008Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.