An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation
An algorithm for stochastic convex-concave fractional programs with applications to production efficiency and equitable resource allocation
复制标题
DOI：
10.1016/j.ejor.2023.12.020
复制
发表时间：
2024-06
影响因子：
6.4
通讯作者：
Shibshankar Dey;Cheolmin Kim;Sanjay Mehrotra
中科院分区：
文献类型：
--
作者：
Shibshankar Dey;Cheolmin Kim;Sanjay Mehrotra
我们提出了一个算法来解决凸和凹分式规划和他们的随机同行在一个共同的框架。我们的方法是基于一种新的重新制定，涉及的平方项的限制，和随后的就业的分段线性近似的凹项的差异。使用分支定界（B&B）框架，我们的算法自适应地细化分段线性逼近和迭代求解凸逼近问题。收敛性分析提供了一个最优性差距的函数的逼近误差的界限。基于这个界，我们证明了所提出的B&B算法在有限次迭代中终止，并且获得最优解的最坏情况界依赖于最优解的平方根. Cobb-Douglas生产效率和公平资源分配问题的数值实验表明，该算法能够有效地找到高精度的解，同时在所有小规模问题的求解实例中显著优于基准算法。改进的分支策略利用凸函数的非线性进一步提高了性能。结果还讨论了当解决一个双重的重新制定和使用切割面算法来解决分布鲁棒对应的Cobb-Douglas示例模型。
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.