MSc., Faculty of Science, University of the Witwatersrand, 2011 / 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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/11074 |
| Date | 18 January 2012 |
| Creators | Fomeni, Franklin Djeumou |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0028 seconds