A deterministic global optimization algorithm. (English) Zbl 1114.65062

The purpose of this paper is to introduce a new deterministic global optimization algorithm to solve a general linear sum of ratios programming problem (LFP). At first, an equivalent optimization problem (LFP1) of LFP is derived by exploiting the characteristics of the constraints of LFP. By a new linearizing method the linearization relaxation function of the objective function of LFP1 is proposed. Then the linear relaxation programming (RLP) of LFP1 is obtained which allows it to be incorporated into a branch-and-bound scheme. The proposed branch and bound algorithm is convergent to the global minimum through the successive refinement of the linear relaxation of the feasible region of the objection function and the solutions of a series of RLP. Finally, the numerical tests show the feasibility and efficiency of the proposed method.


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


[1] Konno, H.; Watanabe, H., Bond portfolio optimization problems and their application to index tracking: a partial optimization approach, Journal of the Operations Research Society of Japan, 39, 295-306 (1996) · Zbl 0873.90009
[2] Konno, H.; Inori, M., Bond portfolio optimization by bilinear fractional programming, Journal of the Operations Research Society of Japan, 32, 143-158 (1989) · Zbl 0675.90011
[3] Charnes, A.; Cooper, W. W., Programming with linear fractional functionk, Naval Research Logistick Quarterly, 9, 181-186 (1962) · Zbl 0127.36901
[4] Konno, H.; Yajima, Y.; Maktkui, T., Parametric simples algorithms for solving a special class of nonconvex minimization problems, Journal of Global Optimization, 1, 65-81 (1991) · Zbl 0746.90056
[5] Konno, H.; Abe, N., Minimization of the sum of three linear fractional functions, Journal of Global Optimization, 15, 419-432 (2002) · Zbl 0961.90115
[6] 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
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.