A global optimization algorithm for linear fractional programming (Q2378922)

The authors consider the class of fractional maximization problems, in which the sum of ratios of linear functions is maximized on a given convex polyhedron \(\{x\in\mathbb R^n\); \(Ax\leq b\), \(x\geq 0\}\). It is assumed that the polyhedron has nonempty interior and all denominators occurring in the ratios of the fractional objective function are different from zero. An equivalent problem to this optimization problem is derived and solved using a linear relaxation method. The proposed solution method is based on the branch and bound approach, consists in solving a sequence of linear programming problems and is convergent to the global maximum. Comparison with other methods in the literature is presented. Numerical experiments showing the effectivity of the proposed method are reported in the concluding part of the paper.