A semidefinite programming based branch-and-bound framework for the quadratic assignment problem

U. Truetsch

Research output: ThesisDoctoral ThesisScientific

388 Downloads (Pure)

Abstract

The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart" choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respective bound and the capability of being applicable to symmetry reduction. A byproduct of this part of the thesis are some best known lower bounds for some QAPLIB instances. The second part of this thesis considers different kinds of heuristics for the quadratic assignment problem in order to find a good upper bound. Amongst others, we present a new quadratic programming-based heuristic for the QAP. For this purpose, we provide a technique on how to derive a feasible solution for the QAP in polynomial time using Karush-Kuhn-Tucker points of a quadratic programming reformulation. Further, we also present well-known heuristics for the QAP as the iterated local search heuristic and simulated annealing. With final “smart” choices of different branching strategies and of the use of respective heuristics and relaxations, we came up with a new SDP-based branch-and-bound framework that successfully reduces the number of node counts in a branching tree compared to other branch-and-bound frameworks from literature.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • de Klerk, Etienne, Promotor
  • Sotirov, Renata, Promotor
Award date31 Oct 2014
Place of PublicationTilburg
Publisher
Print ISBNs9789056684068
Publication statusPublished - 31 Oct 2014

Fingerprint

Quadratic programming
Simulated annealing
Byproducts
Polynomials
Local search (optimization)

Cite this

Truetsch, U. (2014). A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. Tilburg: CentER, Center for Economic Research.
Truetsch, U.. / A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. Tilburg : CentER, Center for Economic Research, 2014. 163 p.
@phdthesis{ff97cfeaa5da41e083160c27a848c6ec,
title = "A semidefinite programming based branch-and-bound framework for the quadratic assignment problem",
abstract = "The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a {"}smart{"} choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respective bound and the capability of being applicable to symmetry reduction. A byproduct of this part of the thesis are some best known lower bounds for some QAPLIB instances. The second part of this thesis considers different kinds of heuristics for the quadratic assignment problem in order to find a good upper bound. Amongst others, we present a new quadratic programming-based heuristic for the QAP. For this purpose, we provide a technique on how to derive a feasible solution for the QAP in polynomial time using Karush-Kuhn-Tucker points of a quadratic programming reformulation. Further, we also present well-known heuristics for the QAP as the iterated local search heuristic and simulated annealing. With final “smart” choices of different branching strategies and of the use of respective heuristics and relaxations, we came up with a new SDP-based branch-and-bound framework that successfully reduces the number of node counts in a branching tree compared to other branch-and-bound frameworks from literature.",
author = "U. Truetsch",
year = "2014",
month = "10",
day = "31",
language = "English",
isbn = "9789056684068",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

Truetsch, U 2014, 'A semidefinite programming based branch-and-bound framework for the quadratic assignment problem', Doctor of Philosophy, Tilburg University, Tilburg.

A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. / Truetsch, U.

Tilburg : CentER, Center for Economic Research, 2014. 163 p.

Research output: ThesisDoctoral ThesisScientific

TY - THES

T1 - A semidefinite programming based branch-and-bound framework for the quadratic assignment problem

AU - Truetsch, U.

PY - 2014/10/31

Y1 - 2014/10/31

N2 - The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart" choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respective bound and the capability of being applicable to symmetry reduction. A byproduct of this part of the thesis are some best known lower bounds for some QAPLIB instances. The second part of this thesis considers different kinds of heuristics for the quadratic assignment problem in order to find a good upper bound. Amongst others, we present a new quadratic programming-based heuristic for the QAP. For this purpose, we provide a technique on how to derive a feasible solution for the QAP in polynomial time using Karush-Kuhn-Tucker points of a quadratic programming reformulation. Further, we also present well-known heuristics for the QAP as the iterated local search heuristic and simulated annealing. With final “smart” choices of different branching strategies and of the use of respective heuristics and relaxations, we came up with a new SDP-based branch-and-bound framework that successfully reduces the number of node counts in a branching tree compared to other branch-and-bound frameworks from literature.

AB - The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart" choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respective bound and the capability of being applicable to symmetry reduction. A byproduct of this part of the thesis are some best known lower bounds for some QAPLIB instances. The second part of this thesis considers different kinds of heuristics for the quadratic assignment problem in order to find a good upper bound. Amongst others, we present a new quadratic programming-based heuristic for the QAP. For this purpose, we provide a technique on how to derive a feasible solution for the QAP in polynomial time using Karush-Kuhn-Tucker points of a quadratic programming reformulation. Further, we also present well-known heuristics for the QAP as the iterated local search heuristic and simulated annealing. With final “smart” choices of different branching strategies and of the use of respective heuristics and relaxations, we came up with a new SDP-based branch-and-bound framework that successfully reduces the number of node counts in a branching tree compared to other branch-and-bound frameworks from literature.

M3 - Doctoral Thesis

SN - 9789056684068

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Truetsch U. A semidefinite programming based branch-and-bound framework for the quadratic assignment problem. Tilburg: CentER, Center for Economic Research, 2014. 163 p. (CentER Dissertation Series).