| dc.description.abstract | 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. | en |
