An adaptive branch-and-bound algorithm for minimax linear fractional programming
摘要
This paper proposes an adaptive branch-and-bound algorithm to solve the minimax linear fractional programming (MLFP) problem. We initially utilize the Charnes-Cooper transformation and introduce an auxiliary variable to convert (MLFP) into an equivalent problem (EP). A linear relaxation problem of (EP) is then constructed by applying a new two-phase linearization technique on the one-dimensional interval. Subsequently, to avoid invalid computations, we propose a novel adaptive branching rule to distinguish it from traditional bisection. The proposed rule ensures that, under specific conditions, the feasible regions of the relaxation subproblems after branching exclude the point that is optimal for the relaxation problem on the selected branch. Consequently, it guarantees monotonic improvement of the lower bound on the optimal value of (MLFP). Also, we prove the convergence of the algorithm, and estimate the definitive maximum on the number of iterations required. Finally, the numerical results illustrate the effectiveness and robustness of the proposed algorithm for test instances.