Solving the sum-of-ratios problem by a stochastic search algorithm
In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.
|Keywords||Sum-of-ratios problems, Min-max problems, Dinkelbach-type method, Branch-and-bound method, Stochastic search method|
|Persistent URL||dx.doi.org/10.1007/s10898-008-9285-y, hdl.handle.net/1765/117998|
|Journal||Journal of Global Optimization|
Wu, W.Y., Sheu, R.L., & Birbil, S.I. (2008). Solving the sum-of-ratios problem by a stochastic search algorithm. Journal of Global Optimization, 42(1), 91–109. doi:10.1007/s10898-008-9285-y