Branch-Relaxation-Bound Algorithm for Minimizing a Class of Sum of Affine Ratios Programming Problems

This paper introduces a branch-relaxation-bound algorithm (BRBA) designed to minimize a class of sum of affine ratios programming (SARP) problems. By leveraging the structural characteristics of SARP, we present a novel relaxation technique that facilitates the construction of a sequence of affine relaxation problems. To optimize computational efficiency, the branching operation is conducted in the output space whose dimension is equal to the number of denominators. By integrating the branch-and-bound framework with affine relaxation problems, a branch-relaxation-bound algorithm is developed. Subsequently, we demonstrate the convergence of the algorithm and discuss its computational complexity. Finally, numerical experiments confirm the feasibility and effectiveness of the proposed algorithm.