A branch-and-cut algorithm for a class of sum-of-ratios problems

摘要

The problem of maximizing a sum of concave–convex ratios over a convex set is addressed. The projection of the problem onto the image space of the functions that describe the ratios leads to the equivalent problem of maximizing a sum of elementary ratios subject to a linear semi-infinite inequality constraint. A global optimization algorithm that integrates a branch-and-bound procedure for dealing with nonconcavities in the image space and an efficient relaxation procedure for handling the semi-infinite constraint is proposed and illustrated through numerical examples. Comparative (computational) analyses between the proposed algorithm and two alternative algorithms for solving sum-of-ratios problems are also presented.