Globally addressing minmax linear fractional problem
摘要
This paper presents a branch-and-bound algorithm for addressing minmax linear fractional problem. To begin, we reformulate the original problem into an equivalent problem by introducing auxiliary variables and applying the Charnes-Cooper transformation. Next, a linear relaxation technique is employed to linearize the nonlinear constraints of the equivalent problem, yielding a corresponding linear relaxation problem. Subsequently, based on the outer space partitioning search, we propose an outer space branch-and-bound algorithm for the minmax linear fractional problem by updating the lower bound through calculating the relaxation problem and updating the upper bound through calculating the objective function value of feasible point of the original problem. Additionally, a rigorous proof of the algorithm’s convergence is provided, along with an analysis of its computational complexity, leading to an estimation of the maximum number of iterations required. Numerical experiments confirm the algorithm’s robustness and demonstrate its computational efficiency.