A spatial branching and cutting algorithm for minimizing the sum of affine fractional functions
摘要
We consider the problem of minimizing the sum of affine fractional functions (SAFF) over polyhedra. Initially, we transform problem (SAFF) into an equivalent problem, and proceed to construct its relaxation and enhanced relaxation. Then, we propose a novel spatial branching rule (SBR) and integrate it with the relaxations, resulting in a spatial branching and cutting algorithm. The proposed algorithm guarantees that in each iteration, the computed optimal solution of the relaxation problem corresponding to the minimum lower bound of the optimal value of problem (SAFF) is cut off. Furthermore, we analyze the convergence and complexity of the constructed algorithm. The numerical experiments validate the effectiveness of the proposed algorithm.