EFFECTIVE ALGORITHM AND COMPUTATIONAL COMPLEXITY FOR SOLVING SUM OF LINEAR RATIOS PROBLEM

This paper presents an effective algorithm for globally solving the sum of linear ratios problem (SLRP), which has broad applications in govern-ment planning, finance and investment, cluster analysis, game theory and so on. In this paper, by using a new linearization technique, the linear relaxation problem of the equivalent problem is constructed. Next, based on the linear relaxation problem and the branch-and-bound framework, an effective branch-and-bound algorithm for globally solving the problem (SLRP) is proposed. By analyzing the computational complexity of the proposed algorithm, the maxi-mum number of iterations of the algorithm is derived. Numerical experiments are reported to verify the effectiveness and feasibility of the proposed algo-rithm. Finally, two practical application problems from power transportation and production planning are solved to verify the feasibility of the algorithm.