New solution approaches for the quadratic assignment problem

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Fomeni, Franklin Djeumou
dc.date.accessioned 2012-01-18T08:50:56Z
dc.date.available 2012-01-18T08:50:56Z
dc.date.issued 2012-01-18
dc.identifier.uri http://hdl.handle.net/10539/11074
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


Advanced Search

Browse

My Account

Statistics