A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives

E. de Klerk, R. Sotirov, U. Truetsch

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB (Quadratic Assignment Problem Library) test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances.
Original languageEnglish
Pages (from-to)378–391
JournalINFORMS Journal on Computing
Volume27
Issue number2
DOIs
Publication statusPublished - 4 May 2015

Fingerprint

Quadratic programming
Linear programming
Quadratic assignment problem
Semidefinite programming
Symmetry group

Cite this

@article{9efcb7c3451b480a98b4b2e29e9acb89,
title = "A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives",
abstract = "Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB (Quadratic Assignment Problem Library) test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances.",
author = "{de Klerk}, E. and R. Sotirov and U. Truetsch",
year = "2015",
month = "5",
day = "4",
doi = "10.1287/ijoc.2014.0634",
language = "English",
volume = "27",
pages = "378–391",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "2",

}

A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives. / de Klerk, E.; Sotirov, R.; Truetsch, U.

In: INFORMS Journal on Computing, Vol. 27, No. 2, 04.05.2015, p. 378–391.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives

AU - de Klerk, E.

AU - Sotirov, R.

AU - Truetsch, U.

PY - 2015/5/4

Y1 - 2015/5/4

N2 - Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB (Quadratic Assignment Problem Library) test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances.

AB - Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB (Quadratic Assignment Problem Library) test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidefinite programming (SDP) bounds for QAPs have also been studied in some detail, but their computational impact has been limited so far, mostly because of the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work, we introduce a new SDP relaxation, where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature. In particular, we compute the best-known lower bounds for two QAPLIB instances.

U2 - 10.1287/ijoc.2014.0634

DO - 10.1287/ijoc.2014.0634

M3 - Article

VL - 27

SP - 378

EP - 391

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 2

ER -