  


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,71109, 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 Modify/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  