An Effective Computational Algorithm for the Global Solution of a Class of Linear Fractional Programming

Abstract EN

For the minimization of the sum of linear fractions on polyhedra, it is likewise a class of linear fractional programming (LFP).

In this paper, we mainly propose a new linear relaxation technique and combine the branch-and-bound algorithm framework to solve the LFP globally.

It is worthwhile to mention that the branching operation of the algorithm occurs in the relatively small output space of the dimension rather than the space where the decision variable is located.

When the number of linear fractions in the objective function is much lower than the dimension of the decision variable, the performance of the algorithm is better.

After that, we also explain the effectiveness, feasibility, and other performances of the algorithm through numerical experiments.