Parametric approaches to fractional programs: Analytical and empirical study

<p>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.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Management

Year

2016

Author dc:creator

• Park, Chong Hyun

Contributors dc:contributor

• Robert Plante
• Yanjun Li
• Gemma Berenguer
• Jen Tang

• Applied sciences
• Complexity
• Fractional programming
• Numerical optimization
• Polynomial time algorithm
• Applied Mathematics
• Operational Research

Repository record dc:identifier

https://docs.lib.purdue.edu/open_access_dissertations/825

OAI identifier oai:identifier

oai:docs.lib.purdue.edu:open_access_dissertations-2017