×

A branch and bound algorithm to globally solve the sum of several linear ratios. (English) Zbl 1079.65071

The authors develop a branch and bound globally convergent algorithm for optimizing the sum of several linear fractional functions over a polytope by solving a series of linear programming problems. Some numerical results are presented.

MSC:

65K05 Numerical mathematical programming methods
90C32 Fractional programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Charnes, A.; Cooper, W. W., Programming with linear fractional functions, Naval Research Logistics Quarterly, 9, 181-186 (1962) · Zbl 0127.36901
[2] Konno, H.; Yajima, Y.; Matsui, T., Parametric simplex algorithms for solving a special class of nonconvex minimization problems, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[3] Konno, H.; Abe, N., Journal of Global Optimization, 15, 419-432 (2002) · Zbl 0961.90115
[4] Kuno, T., A branch-and-bound algorithm for maximizing the sum of several linear ratios, Journal of Global Optimization, 22, 155-174 (2002) · Zbl 1045.90071
[5] H. Konno, H. Yamashita, Minimization of the sum and the product of several linear fractional functions, Tokyo Institute of Technology, Technical Report, 1997.; H. Konno, H. Yamashita, Minimization of the sum and the product of several linear fractional functions, Tokyo Institute of Technology, Technical Report, 1997.
[6] Konno, H.; Kuno, T.; Yajima, Y., Global minimization of a generalized convex multiplicative function, Journal of Global Optimization, 4, 47-62 (1994) · Zbl 0791.90045
[7] Benson, H. P., Using concave envelopes to globally solve the nonlinear sum of ratios problem, Journal of Global Optimization, 22, 343-364 (2002) · Zbl 1045.90069
[8] Sherali, H. D., Global optimization of nonconvex polynomial programming problems having ratilnal exponents, Journal of Global Optimization, 12, 267-283 (1998) · Zbl 0905.90146
[9] Horst, R.; Tuy, H., Global Optimization, Deterministic Approaches (1990), Springer-Verlag: Springer-Verlag Berlin · Zbl 0704.90057
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.