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/2006
Entry Accepted: 10/27/2006
Entry Last Modified: 04/19/2008

Modify/Update this entry