The unrestricted linear fractional assignment problem

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.