Date of Award

8-2016

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Management

First Advisor

Robert Plante

Second Advisor

Yanjun Li

Committee Chair

Robert Plante

Committee Co-Chair

Yanjun Li

Committee Member 1

Gemma Berenguer

Committee Member 2

Jen Tang

Abstract

Fractional programming is used to model problems where the objective function is a ratio of functions. A parametric modeling approach provides effective technique for obtaining optimal solutions of these fractional programming problems. Although many heuristic algorithms have been proposed and assessed relative to each other, there are limited theoretical studies on the number of steps to obtain the solution. In this dissertation, I focus on the linear fractional combinatorial optimization problem, a special case of fractional programming where all functions in the objective function and constraints are linear and all variables are binary that model certain combinatorial structures. Two parametric algorithms are considered and the efficiency of the algorithms is investigated both theoretically and computationally. I develop the complexity bounds for these algorithms, and show that they can solve the linear fractional combinatorial optimization problem in polynomial time. In the computational study, the algorithms are used to solve fractional knapsack problem, fractional facility location problem, and fractional transportation problem by comparison to other algorithms (e.g., Newton's method). The relative practical performance measured by the number of function calls demonstrates that the proposed algorithms are fast and robust for solving the linear fractional programs with discrete variables.

Download

Share

COinS