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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Park, Chong Hyun"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Management","degree_department":null,"school":null,"contributors":["Robert Plante","Yanjun Li","Gemma Berenguer","Jen Tang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-08-01T07:00:00Z","date_published":"2016-08-01T07:00:00Z","updated_at":"2026-07-24T03:54:02Z","subjects":["Applied sciences","Complexity","Fractional programming","Numerical optimization","Polynomial time algorithm","Applied Mathematics","Operational Research"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://docs.lib.purdue.edu/open_access_dissertations/825","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Robert Plante","Yanjun Li","Gemma Berenguer","Jen Tang"]},{"key":"dc:creator","label":"Author","values":["Park, Chong Hyun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Management"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Applied sciences","Complexity","Fractional programming","Numerical optimization","Polynomial time algorithm","Applied Mathematics","Operational Research"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://docs.lib.purdue.edu/open_access_dissertations/825"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Parametric approaches to fractional programs: Analytical and empirical study"]}]}],"canonical_facts":{"dc:contributor":["Robert Plante","Yanjun Li","Gemma Berenguer","Jen Tang"],"dc:creator":["Park, Chong Hyun"],"dc:description.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.
"],"dc:identifier":["https://docs.lib.purdue.edu/open_access_dissertations/825"],"dc:subject":["Applied sciences","Complexity","Fractional programming","Numerical optimization","Polynomial time algorithm","Applied Mathematics","Operational Research"],"dc:title":["Parametric approaches to fractional programs: Analytical and empirical study"],"thesis:degree_discipline":["Management"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:54:02Z"}