IMAGE SPACE BRANCH-AND-BOUND ALGORITHM FOR GLOBALLY SOLVING MINIMAX LINEAR FRACTIONAL PROGRAMMING PROBLEM

摘要

This paper presents an image space branch-and-bound algorithm for a minimax linear fractional programming problem (MLFP), which is widely used in data envelopment analysis, system identification and so on. In this algorithm, based on equivalent transformation and new linearizing technique, we convert the original problem into a linear relaxation programming problem, which can be used to calculate the lower bound of the optimal value of the original problem. By subsequently refining the initial image space region and successively solving a series of linear relaxation problems, the proposed algorithm is globally convergent to the optimal solution of the problem (MLFP). By analyzing the computational complexity of the algorithm, we give a maximum evaluation of number of iterations of the algorithm for the first time. Finally, numerical experimental results demonstrate the feasibility and effectiveness of the proposed algorithm.