The optimal assignment problem: an investigation into current solutions, new approaches and the doubly stochastic polytope

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Vermaak, Frans-Willem
dc.date.accessioned 2011-05-23T10:56:39Z
dc.date.available 2011-05-23T10:56:39Z
dc.date.issued 2011-05-23
dc.identifier.uri http://hdl.handle.net/10539/9894
dc.description MSc(Eng),Faculty of Engineering and the Built Environment, University of the Witwatersrand, 2010 en_US
dc.description.abstract This dissertation presents two important results: a novel algorithm that approximately solves the optimal assignment problem as well as a novel method of projecting matrices into the doubly stochastic polytope while preserving the optimal assignment. The optimal assignment problem is a classical combinatorial optimisation problem that has fuelled extensive research in the last century. The problem is concerned with a matching or assignment of elements in one set to those in another set in an optimal manner. It finds typical application in logistical optimisation such as the matching of operators and machines but there are numerous other applications. In this document a process of iterative weighted normalization applied to the benefit matrix associated with the Assignment problem is considered. This process is derived from the application of the Computational Ecology Model to the assignment problem and referred to as the OACE (Optimal Assignment by Computational Ecology) algorithm. This simple process of iterative weighted normalisation converges towards a matrix that is easily converted to a permutation matrix corresponding to the optimal assignment or an assignment close to optimality. The document also considers a method of projecting a matrix into the doubly stochastic polytope while preserving the optimal assignment. Various methods of projecting square matrices into the doubly stochastic polytope exist but none that preserve the assignment. This novel result could prove instrumental in solving assignment problems and promises applications in other optimisation algorithms similar to those that Sinkhorn’s algorithm finds. en_US
dc.language.iso en en_US
dc.subject systems engineering en_US
dc.subject optimal assignment problem en_US
dc.subject doubly stochastic polytope en_US
dc.subject optimisation algorithms en_US
dc.title The optimal assignment problem: an investigation into current solutions, new approaches and the doubly stochastic polytope 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


Browse

My Account

Statistics