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

Gao, Lianbo; Mishra, Shashi K.; Shi, Jianming

Optim. Lett. 6, No. 2, 221-230 (2012).

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.

MSC:

90C30	Nonlinear programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

sum-of-linear (nonlinear)-ratios problem; \({\mathcal{NP}}\)-hard; branch-and-bound approach

References:

[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)