A branch-and-bound algorithm for maximizing the sum of several linear ratios

In this paper, we develop a branch-and-bound algorithm for maximizing a sum of p (greater than or equal to2) linear ratios on a polytope. The problem is embedded into a 2p-dimensional space, in which a concave polyhedral function overestimating the optimal value is constructed for the bounding operation. The branching operation is carried out in a p-dimensional space, in a way similar to the usual rectangular branch-and-bound method. We discuss the convergence properties and report some computational results.