New solution approaches for the quadratic assignment problem
Date
2012-01-18
Authors
Fomeni, Franklin Djeumou
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A vast array of important practical problems, in many di erent elds, can be modelled and
solved as quadratic assignment problems (QAP). This includes problems such as university
campus layout, forest management, assignment of runners in a relay team, parallel and
distributed computing, etc. The QAP is a di cult combinatorial optimization problem
and solving QAP instances of size greater than 22 within a reasonable amount of time
is still challenging. In this dissertation, we propose two new solution approaches to the
QAP, namely, a Branch-and-Bound method and a discrete dynamic convexized method.
These two methods use the standard quadratic integer programming formulation of the
QAP. We also present a lower bounding technique for the QAP based on an equivalent
separable convex quadratic formulation of the QAP. We nally develop two di erent new
techniques for nding initial strictly feasible points for the interior point method used in
the Branch-and-Bound method. Numerical results are presented showing the robustness
of both methods.
Description
MSc., Faculty of Science, University of the Witwatersrand, 2011
Keywords
Graph theory, Combinatorial optimization, Quadratic programming, Computer science (mathematics)