New solution approaches for the quadratic assignment problem

dc.contributor.authorFomeni, Franklin Djeumou
dc.date.accessioned2012-01-18T08:50:56Z
dc.date.available2012-01-18T08:50:56Z
dc.date.issued2012-01-18
dc.descriptionMSc., Faculty of Science, University of the Witwatersrand, 2011en_US
dc.description.abstractA 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.identifier.urihttp://hdl.handle.net/10539/11074
dc.language.isoenen_US
dc.subjectGraph theoryen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectQuadratic programmingen_US
dc.subjectComputer science (mathematics)en_US
dc.titleNew solution approaches for the quadratic assignment problemen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
franklin.pdf
Size:
1.31 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Collections