Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem

Abstract

This paper proposes an efficient method for acquiring the global solution of the sum of affine ratios problem (SARP) in the reduced outer space. Using equivalence conversions, the original problem was transformed into an equivalent problem. Then, an affine relaxation problem of the equivalent problem was constructed by exploiting linearization techniques. Subsequently, an outcome space branch-and-bound algorithm was proposed, the convergence of the algorithm was proved and the computational complexity was estimated. Finally, numerical examples were presented to demonstrate the effectiveness and feasibility of the presented algorithm.

Keywords

• fractional programs
• global optimization
• sum of affine ratios problems
• linearization technique
• outcome space branch-and-bound algorithm