An outcome space algorithm for minimizing a class of linear ratio optimization problems

This paper presents an outcome space branch-and-bound algorithm for minimizing a class of linear ratio optimization problems (LROPs), requiring just nonnull denominators in the given domain. The solution methodology uses an affine relaxation of a bilinear approximation model, which is equivalent to the original problem. By combining the relaxation model with the branch-and-bound framework, an outcome space branch-and-bound algorithm is devised for solving LROPs. The algorithm can reduce the computational complexity, as branching is performed in the outcome space with a size equal to the number of fractions, rather than the variable dimension space. Finally, the numerical results indicate the computational feasibility and good performance of the algorithm.