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

Chong Hyun Park, Heejong Lim

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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.

Original languageEnglish
Pages (from-to)1030-1039
Number of pages10
JournalEuropean Journal of Operational Research
Volume289
Issue number3
DOIs
StatePublished - 16 Mar 2021

Keywords

  • Complexity
  • Fractional programming
  • Parametric algorithm
  • Road maintenance planning

Fingerprint

Dive into the research topics of 'A parametric approach to integer linear fractional programming: Newton's and Hybrid-Newton methods for an optimal road maintenance problem'. Together they form a unique fingerprint.

Cite this