Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Etienne de Klerk(E.deKlerkuvt.nl)
Renata Sotirov(R.Sotirovuvt.nl)

Abstract: Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71--109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in: [E. de Klerk and R. Sotirov. Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Mathematical Programming A, (to appear)]. Continuing in the same vein, we show how one may obtained stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.

Keywords: quadratic assignment problem, semidefinite programming, group symmetry, branch and bound

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization

Citation: CentER Discussion Paper Tilburg University, The Netherlands, September 2009.

Download: [PDF]

Entry Submitted: 09/17/2009
Entry Accepted: 09/17/2009
Entry Last Modified: 09/17/2009

Modify/Update this entry