The minimax linear fractional programming problem with binary variables

The single ratio linear fractional programming problem when the denominator of the objective function ratio is non-negative is solvable in polynomial time. This result extends to several classes of optimization problems with binary variables. However, when the denominator is allowed to take both positive and negative values, even the unconstrained problem with binary variables is NP-hard. Generalization of this problem where a sum of ratios is also well studied. Experimental results on this however are restricted to non-negative denominators. In this thesis we consider the minimax version of the multi-ratio problem with binary variables. The continuous version of the minimax problem is also well-studied but to the best of our knowledge not much research work has been done on the binary version. We present various mathematical programming formulations of the problem for the case of non-negative denominators as well as arbitrary denominators. We also present algorithms to overcome some of the computational difficulties. Extensive computational analysis has been carried under the scenarios of unconstrained problems, problems with a knapsack constraint, and problems with assignment constraints to assess the relative merits of the models. The analysis disclosed some interesting insights into the structure of the problems.