The Multiplicative Assignment Problem

Author: 
Date created: 
2017-07-06
Identifier: 
etd10294
Keywords: 
Quadratic assignment
Multiplicative assignment
Linearization
Constrained assignment
Heuristics
Local search
Tabu search
CPLEX
C++
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 type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Abraham Punnen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Statistics: