Exact Methods In Fractional Combinatorial Optimization

This dissertation considers a subclass of sum-of-ratios fractional combinatorial optimization problems (FCOPs) whose linear versions admit polynomial-time exact algorithms. This topic lies in the intersection of two scarcely researched areas of fractional programming (FP): sum-of-ratios FP and combinatorial FP. Although not extensively researched, the sum-of-ratios problems have a number of important practical applications in manufacturing, administration, transportation, data mining, etc. Since even in such a restricted research domain the problems are numerous, the main focus of this dissertation is a mathematical programming study of the three, probably, most classical FCOPs: Minimum Multiple Ratio Spanning Tree (MMRST), Minimum Multiple Ratio Path (MMRP) and Minimum Multiple Ratio Cycle (MMRC). The first two problems are studied in detail, while for the other one only the theoretical complexity issues are addressed. The dissertation emphasizes developing solution methodologies for the considered family of fractional programs. The main contributions include: (i) worst-case complexity results for the MMRP and MMRC problems; (ii) mixed 0-1 formulations for the MMRST and MMRC problems; (iii) a global optimization approach for the MMRST problem that extends an existing method for the special case of the sum of two ratios; (iv) new polynomially computable bounds on the optimal objective value of the considered class of FCOPs, as well as the feasible region reduction techniques based on these bounds; (v) an efficient heuristic approach; and, (vi) a generic global optimization approach for the considered class of FCOPs. Finally, extensive computational experiments are carried out to benchmark performance of the suggested solution techniques. The results confirm that the suggested global optimization algorithms generally outperform the conventional mixed 0{1 programming technique on larger problem instances. The developed heuristic approach shows the best run time, and delivers near-optimal solutions in most cases.