An extension of branch-and-bound algorithm for solving sum-of-nonlinear-ratios problem. (English) Zbl 1259.90133

Summary: This paper is concerned with a problem of maximizing the sum of several ratios of functions. We extend an algorithm, which has been designed to solve the sum-of-linear-ratios problem, for solving the sum-of-nonlinear-ratios problem. We also discuss the complexity of the problem and report the results of numerical experiments on the extended algorithm.


90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI


[1] Benson H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problem. J. Glob. Optim. 22, 343–364 (2002) · Zbl 1045.90069
[2] Dai Y., Shi J., Wang S.Y.: Conical partition algorithm for maximizing the sum of dc ratios. J. Glob. Optim. 31, 253–270 (2005) · Zbl 1090.90186
[3] Dur M., Horst R., Thoai N.V.: Solving sum-of-ratios fractional programs using efficient points. Optimization 49, 447–466 (2001) · Zbl 1006.90081
[4] Freund R.W., Jarre F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001) · Zbl 1168.90644
[5] Horst R., Tuy H.: Global Optimization: Deterministic Approaches. Springer, Berlin (1996) · Zbl 0867.90105
[6] Karpenko O., Shi J., Dai Y.: Prediction of MHC class II binders using the ant colony search strategy. Artif. Intell. Med. 35, 147–156 (2005) · Zbl 05390820
[7] Konno H., Abe N.: Minimization of the sum of three linear fractional functions. J. Glob. Optim. 15, 419–432 (1999) · Zbl 0961.90115
[8] 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) · Zbl 0971.90065
[9] Konno H., Yajima Y., Matsui T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Glob. Optim. 1, 65–81 (1991) · Zbl 0746.90056
[10] Konno H., Yamashita H.: Minimization of the sum and the product of several linear fractional functions. Nav. Res. Logist. 46, 583–596 (1999) · Zbl 0948.90132
[11] Kuno T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002) · Zbl 1045.90071
[12] Matsui T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9, 113–119 (1996) · Zbl 0868.90111
[13] Muu L.D., Tam B.T., Schaible S.: Efficient algorithms for solving certain nonconvex programs dealing with the product of two affine fractional functions. J. Glob. Optim. 6, 179–191 (1995) · Zbl 0835.90073
[14] Pardalos P.M., Phillips A.: Global optimization of fractional programs. J. Glob. Optim. 1, 173–182 (1991) · Zbl 0748.90068
[15] Phuong N.T.H., Tuy H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259 (2003) · Zbl 1039.90079
[16] Prokopyev O.A., Huang H.-X., Pardalos P.M.: On complexity of unconstrained hyperbolic 0–1 programming problems. Oper. Res. Lett. 33, 312–318 (2005) · Zbl 1140.90469
[17] Schaible S.: A note on the sum of a linear and linear-fractional function. Nav. Res. Logist. Q. 24, 691–693 (1977) · Zbl 0377.90086
[18] Schaible S., Shi J.: Fractional programming: the sum-of-ratios case. Optim. Methods Softw. 18, 219–229 (2003) · Zbl 1070.90115
[19] Schaible, S., Shi, J.: Recent developments in fractional programming: single-ratio and max- min case. In: Nonlinear Analysis and Convex Analysis, pp. 493–506. Yokohama Publishers, Yokohama (2004) · Zbl 1149.90412
[20] Shi J.: A combined algorithm for fractional programming. Ann. Oper. Res. 103, 135–147 (2001) · Zbl 0992.90071
[21] Stancu-Minasian I.M.: Fractional Programming. Kluwer Academic Publishers, Dordrecht (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.