2008
Solving the sum-of-ratios problem by a stochastic search algorithm
Publication
Publication
Journal of Global Optimization , Volume 42 - Issue 1 p. 91- 109
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.
Additional Metadata | |
---|---|
, , , , | |
doi.org/10.1007/s10898-008-9285-y, hdl.handle.net/1765/117998 | |
Journal of Global Optimization | |
Organisation | Department of Econometrics |
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 |