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

U. Truetsch

Research output: ThesisDoctoral Thesis

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 Dive into the research topics of 'A semidefinite programming based branch-and-bound framework for the quadratic assignment problem'. Together they form a unique fingerprint.

Cite this