.png){kind=icon}
.png){kind=icon}
Return
An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2023.12.020.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (B&B) 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 B&B algorithm terminates in a finite number of iterations and the worst-case bound to obtain an ������-optimal solution reciprocally depends on the square root of ������. Numerical experiments on Cobb-Douglas production efficiency and equitable resource allocation problems support that the algorithm efficiently finds a highly accurate solution while significantly outperforming the benchmark algorithms for all the small size problem instances solved. A modified branching strategy that takes the advantage of non-linearity in convex functions further improves the performance. Results are also discussed when solving a dual reformulation and using a cutting surface algorithm to solve distributionally robust counterpart of the Cobb-Douglas example models.
Keywords:
Fractional programming
Second order cone approximation
Branch and bound algorithm
Stochastic production efficiency problem
Equitable resource allocation
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W