Solution approaches to linear fractional programming and its stochastic generalizations using second order cone approximations

Cheolmin Kim, Sanjay Mehrotra

Research output: Contribution to journalArticlepeer-review

Abstract

We consider linear fractional programming problems in a form of which the linear fractional program and its stochastic and distributionally robust counterparts with finite support are special cases. We introduce a novel reformulation that involves differences of square terms in the constraint, subsequently using a piecewise linear approximation for the concave part. Using the resulting second order cone programs (SOCPs), we develop a solution algorithm in the branch and bound framework. Our method iteratively refines the piecewise linear approximations by dividing hyper-rectangles and solves SOCPs to obtain lower bounds for the sub-hyper-rectangles. We derive a bound on the optimality gap as a function of the approximation errors at the iterate and prove that the number of iterations to attain an -optimal solution is in the order of O(√). Numerical experiments show that the proposed algorithm scales better than state-of-the-art linear-programming-based algorithms and commercial solvers to solve linear fractional programs. Specifically, the proposed algorithm achieves two or more digits of accuracy in significantly less time than the time required by the known algorithms on medium to larger size problem instances. Experimental results with Wasserstein ambiguity sets reveal that our reformulation-based approach solves small size distributionally robust linear fractional programs, with the cardinality of support up to 25.

Original languageEnglish (US)
Pages (from-to)945-971
Number of pages27
JournalSIAM Journal on Optimization
Volume31
Issue number1
DOIs
StatePublished - 2021

Keywords

  • Branch and bound algorithm
  • Convergence analysis
  • Distributionally robust optimization
  • Linear fractional programming
  • Second order cone approximations

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Solution approaches to linear fractional programming and its stochastic generalizations using second order cone approximations'. Together they form a unique fingerprint.

Cite this