Skip to main content

The unrestricted linear fractional assignment problem

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2018-04-20
Authors/Contributors
Author: Guo, Jingxin
Abstract
The linear fractional assignment problem (LFAP) is a well-studied combinatorial optimization problem with various applications. It attempts to minimize ratio of two linear functions subject to standard assignment constraints. When the denominator of the objective function is positive, LFAP is solvable in polynomial time. However, when the denominator of the objective function is allowed to take positive and negative values, LFAP is known to be NP-hard. In this thesis, we present two 0-1 programming formulations of LFAP and compare their relative merits using experimental analysis. We also show that LFAP can be solved as a polynomialy bounded sequence of constrained assignment problems. Experimental results using this methodology are also given. Finally, some local search heuristics are developed and analyzed their efficiency using systematic experimental analysis. Our algorithms are able to solve reasonably large size problems within acceptable computational time.
Document
Identifier
etd10653
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
etd10653_JGuo.pdf 507.06 KB

Views & downloads - as of June 2023

Views: 24
Downloads: 3