An adaptive branching rule based branch-and-bound algorithm for generalized affine fractional programming

This paper investigates a class of generalized affine fractional programming (GAFP) problems, which emerge as mathematical models in real-world applications such as computer vision and financial portfolio optimization. To develop an effective algorithm for solving problem GAFP, we first employ the Charnes-Cooper transformation to derive an equivalent problem (EP). By relaxing the fractional terms of EP and introducing new auxiliary variables, the linear relaxation of EP is then structured. Furthermore, we propose a novel adaptive branching rule that can dynamically update the lower bound of the optimal value to EP after each iteration of the algorithm. This eliminates a key disadvantage of conventional bisection algorithms, where the redundant computation may arise from improving the lower bound of EP within the selected partitioned region. The theoretical analysis establishes the convergence properties and computational complexity of the algorithm. Finally, the numerical results for several test problems demonstrate the performance of the proposed algorithm.