A deterministic global optimization algorithm (Q870181)

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.