Effective algorithm and computational complexity for solving sum of linear ratios problem
Hongwei Jiao, Junqiao Ma, Peiping Shen, Yongjian Qiu
Abstract
This paper presents an effective algorithm for globally solving the sum of linear ratios problem (SLRP), which has broad applications in government 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 maximum number of iterations of the algorithm is derived. Numerical experiments are reported to verify the effectiveness and feasibility of the proposed algorithm. Finally, two practical application problems from power transportation and production planning are solved to verify the feasibility of the algorithm.