A global optimization algorithm for linear fractional programming. (English) Zbl 1159.65064

The authors consider the class of fractional maximization problems, in which the sum of ratios of linear functions is maximized on a given convex polyhedron \(\{x\in\mathbb R^n\); \(Ax\leq b\), \(x\geq 0\}\). It is assumed that the polyhedron has nonempty interior and all denominators occurring in the ratios of the fractional objective function are different from zero. An equivalent problem to this optimization problem is derived and solved using a linear relaxation method. The proposed solution method is based on the branch and bound approach, consists in solving a sequence of linear programming problems and is convergent to the global maximum. Comparison with other methods in the literature is presented. Numerical experiments showing the effectivity of the proposed method are reported in the concluding part of the paper.


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


[1] Konno, H.; Yajima, Y.; Matsui, T., Parametric simplex algorithms for solving a special class of nonconvex minimization problem, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[2] Konno, H.; Yamashita, H., Minimizing sums and products of linear fractional functions over a polytope, Naval Research Logistics, 46, 583-596 (1999) · Zbl 0948.90132
[3] Falk, J. E.; Palocsay, S. W., Image space analysis of generalized fractional programs, Journal of Global Optimization, 4, 63-88 (1994) · Zbl 0809.90121
[4] Ji, Y.; Zhang, K. C.; Qu, S. J., A deterministic global optimization algorithm, Applied Mathematics and Computation, 185, 382-387 (2007) · Zbl 1114.65062
[5] Konno, H.; Inori, M., Bond protfolio optimization by bilinear fractional programming, Journal of the Operations Research Society of Japan, 32, 143-158 (1989) · Zbl 0675.90011
[6] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1993), Springer-Verlag: Springer-Verlag Berlin, Germany
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.