Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997]. AMS classification: 90C22, 20Cxx, 70-08.

MoreLess

Year of publication:	2007
Authors:	de Klerk, Etienne ; Sotirov, Renata
Institutions:	Tilburg University, Center for Economic Research
Subject:	quadratic assignment problem \| semidefinite programming \| group sym- metry

More details

Extent:	application/pdf
Series:	Discussion Paper.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series CentER Discussion Paper Number 2007-44
Classification:	C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10011090357