A branch-and-bound algorithm to globally solve the sum of several linear ratios

摘要

In this paper we propose a branch-and-bound algorithm to globally solve the sum of several linear fractional functions over a polytope. For minimizing problem a linear lower bounding function (LLBF) of the objective function is constructed, then a linear programming is obtained which is solved by a simplex algorithm and provides the lower bounding of the optimal value. The proposed branch-and-bound algorithm is convergent to the global minimum through the successive refinement of the solutions of a series of linear programming problems. The numerical experiment is reported to show the effectiveness and feasibility of the proposed algorithm. Also, this method is extended to solve the maximizing problems.