Skip to main content

The Multiplicative Assignment Problem

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2017-07-06
Authors/Contributors
Author: Tian, Jingbo
Abstract
The quadratic assignment problem (QAP) is an extensively studied combinatorial optimization problem. The special case of QAP where the cost matrix is of rank one is called the multiplicative assignment problem (MAP). MAP is not well studied in literature, particularly in terms of experimental analysis of algorithms. In this thesis we present some mixed integer linear programming formulations and compare their selective strength using experimental analysis. We also present exact and heuristic algorithms to solve MAP. Our heuristic algorithms include improvements in existing FPTAs, as well as local search and tabu search enhancements. Results of extensive experimental analyses are also reported.
Document
Identifier
etd10294
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Punnen, Abraham
Member of collection
Download file Size
etd10294_JTian.pdf 568.45 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0