Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Almogy Y., Levin O.: A class of fractional programming problems. Oper. Res. 19, 57–67 (1971)
Avriel, M., Diewert, W.E., Schaible, S., Zang, I.: Generalized Concavity. Plenum Press (1988)
Barros A.I., Frenk J.B.G., Schaible S., Zhang S.: A new algorithm for generalized fractional programs. Math. Program. 72, 147–175 (1996)
Benson H.P.: Global optimization of nonlinear sums of ratios. J. Math. Anal. Appl. 263, 301–315 (2001)
Benson H.P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theor. Appl. 112, 1–29 (2002)
Benson H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problems. J. Glob. Optim. 22, 343–364 (2002)
Benson H.P.: On the global optimization of sums of linear fractional functions over a convex set. J. Optim. Theor. Appl. 121, 19–39 (2004)
Birbil Ş.İ., Fang S.C.: An electromagnetism-like mechanism for global optimization. J. Glob. Optim. 25, 263–282 (2003)
Birbil Ş.İ., Fang S.C., Sheu R.L.: On the convergence of a population-based global optimization algorithm. J. Glob. Optim. 30, 301–318 (2004)
Cambini A., Martein L., Schaible S.: On maximizing a sum of ratios. J. Inform. Optim. Sci. 10, 65–79 (1989)
Frenk J.B.G., Schaible S.: Fractional programming. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, vol. II, pp. 162–172. Kluwer Publishers, Dordrecht (1989)
Freund R.W., Jarre F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)
Ibaraki T.: Parametric approaches to fractional programs. Math. Program. 26, 345–362 (1983)
Ingber L.: Simulated annealing: practice versus theory. Math. Comput. Modell. 18, 29–57 (1993)
Konno H., Abe N.: Minimization of the sum of three linear fractional functions. J. Glob. Optim. 15, 419–432 (1999)
Konno H., Fukaishi K.: A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems. J. Glob. Optim. 18, 283–299 (2000)
Konno H., Inori M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1989)
Kuno T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002)
Kuno T., Yajima Y., Konno H.: An outer approximation method for minimizing the product of several convex functions on a convex set. J. Glob. Optim. 3, 325–335 (1993)
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag xvi+340 (1994)
Phuong N.T.H., Tuy H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259 (2003)
Rinnooy-Kan A.H.G., Timmer G.T.: Stochastic global optimization methods. II. Multilevel methods. Math. Program. 39, 57–78 (1987)
Schaible S.: Recent results in fractional programming. Oper. Res. Verfahren 23, 271–272 (1977)
Wood G.R.: Multidimensional bisection applied to global optimisation. Comput. Math. Appl. 21, 161–172 (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, WY., Sheu, RL. & Birbil, Ş.İ. Solving the sum-of-ratios problem by a stochastic search algorithm. J Glob Optim 42, 91–109 (2008). https://doi.org/10.1007/s10898-008-9285-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9285-y