A New branch-and-cut algorithm for linear sum-of-ratios problem based on SLO method and LO relaxation

We consider a linear sum-of-ratios fractional programming problem that arises from a broad range of applications and is known to be NP-hard. In this paper, we first develop a successive linear optimization (SLO) method for the linear sum-of-ratios problem and show that it converges to a KKT point of the underlying problem. Second, we propose a new branch-and-cut algorithm for globally solving the linear sum-of-ratios fractional program by integrating the SLO method, the linear optimization (LO) relaxation, branch-and-bound framework and branch-and-cut rule. We establish the global convergence of the algorithm and estimate its complexity. Numerical results are reported to illustrate the effectiveness of the proposed algorithm in finding a global optimal solution to large-scale instances of linear sum-of-ratios problem.