Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  31 Oct 2014 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  9789056684068 
Publication status  Published  31 Oct 2014 
Fingerprint
Cite this
}
A semidefinite programming based branchandbound framework for the quadratic assignment problem. / Truetsch, U.
Tilburg : CentER, Center for Economic Research, 2014. 163 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  A semidefinite programming based branchandbound 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 branchandbound 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 programmingbased 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 KarushKuhnTucker points of a quadratic programming reformulation. Further, we also present wellknown 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 SDPbased branchandbound framework that successfully reduces the number of node counts in a branching tree compared to other branchandbound frameworks from literature.
AB  The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branchandbound 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 programmingbased 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 KarushKuhnTucker points of a quadratic programming reformulation. Further, we also present wellknown 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 SDPbased branchandbound framework that successfully reduces the number of node counts in a branching tree compared to other branchandbound frameworks from literature.
M3  Doctoral Thesis
SN  9789056684068
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 