A parametric approach to integer linear fractional programming: Newton’s and Hybrid-Newton methods for an optimal road maintenance problem

Chong Hyun Park and Heejong Lim

European Journal of Operational Research, 2021, vol. 289, issue 3, 1030-1039

Abstract: In this paper we study a parametric approach, one of the resolution methods for solving integer linear fractional programming (ILFP) problems in which all functions in the objective and constraints are linear and all variables are integers. We develop a novel complexity bound of Newton’s method applied to ILFP problems when variables are bounded. The analytical result for the worst-case performance shows that the number of iterations of Newton’s algorithm to find an optimal solution of the ILFP problem is polynomially bounded. We also propose a Hybrid-Newton algorithm and empirically show that it is relatively faster and more robust than the Newton algorithm under various data scenarios. To illustrate the applicability of our algorithm and provide concrete managerial prescriptions, we consider a case study of a road maintenance planning problem in Seoul, Korea. The results show that our fractional efficiency measure is capable of obtaining the maximum cost-efficient lifetime of a road given a limited maintenance budget.

Keywords: Fractional programming; Complexity; Parametric algorithm; Road maintenance planning (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719305740
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:3:p:1030-1039

DOI: 10.1016/j.ejor.2019.07.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().