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

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.