Ursulenko, Oleksii (2009-12). Exact Methods In Fractional Combinatorial Optimization. Doctoral Dissertation. Thesis uri icon

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.
  • 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.

publication date

  • December 2009