Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework
type: Item
instance of: scholarly article
title: Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework
zbMATH Open document ID: 1180.90169
DOI: 10.1504/IJMOR.2009.022879
author: Frédéric Roupin
published in: International Journal of Mathematics in Operational Research
publication date: 2009-10-12T00:00:00Z
review text: Summary: We consider partial Lagrangian relaxations of continuous quadratic formulations of the quadratic assignment problem (QAP) where the assignment constraints are not relaxed. These relaxations are a theoretical limit for semidefinite relaxations of the QAP using any linearised quadratic equalities made from the assignment constraints. Using this framework, we survey and compare standard semidefinite relaxations of this classical NP-hard problem. In particular, this approach is a simple way to prove that some well-known semidefinite relaxations for the QAP are equivalent. Nevertheless, these relaxations have a different numerical behaviour and practical usefulness depending on the semidefinite programming solver. We discuss such issues by reporting some computational experiments.
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 5613388
zbMATH Keywords: Lagrangian relaxation
zbMATH Keywords: QAP
zbMATH Keywords: quadratic assignment problem
zbMATH Keywords: SDP
zbMATH Keywords: semidefinite programming
MaRDI profile type: Publication
full work available at URL: ijmor.2009.022879
OpenAlex ID: W2128247163
description: scientific article; zbMATH DE number 5613388