Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
Etienne de Klerk(E.deKlerkuvt.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.
Entry Submitted: 09/17/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|