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

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.