We propose an algorithm to solve convex and concave fractional programs and their stochastic counterparts in a common framework. Our approach is based on a novel reformulation that involves differences of square terms in the constraints, and subsequent employment of piecewise-linear approximations of the concave terms. Using the branch-and-bound framework, our algorithm adaptively refines the piecewise-linear approximations and iteratively solves convex approximation problems. The convergence analysis provides a bound on the optimality gap as a function of approximation errors. Based on this bound, we prove that the proposed branch-and-bound algorithm terminates in a finite number of iterations and the worst-case bound to obtain an $\epsilon$-optimal solution reciprocally depends on the square root of $\epsilon$. Numerical experiments on Cob-Douglas production efficiency and equitable resource allocation problems support that the algorithm efficiently finds a highly accurate solution. Specifically, it achieves five-digit accuracy for small size problem instances in reasonable amounts of time while benchmark algorithms only attain two or three digits of accuracy even after running for 12 hours. Moreover, our approaches based on a dual reformulation and a cutting surface algorithm solve the same size of distributionally robust Cob-Douglas production efficiency programs with a little extra computational effort.

## Article

Download

View An Algorithm for Stochastic Convex-Concave Fractional Programs with Applications to Production Efficiency and Equitable Resource Allocation