New solution approaches for the quadratic assignment problem

Show simple item record Fomeni, Franklin Djeumou 2012-01-18T08:50:56Z 2012-01-18T08:50:56Z 2012-01-18
dc.description MSc., Faculty of Science, University of the Witwatersrand, 2011 en_US
dc.description.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. en_US
dc.language.iso en en_US
dc.subject Graph theory en_US
dc.subject Combinatorial optimization en_US
dc.subject Quadratic programming en_US
dc.subject Computer science (mathematics) en_US
dc.title New solution approaches for the quadratic assignment problem en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search WIReDSpace


My Account