Search

This paper presents an efficient outer space branch-and-bound algorithm for globally solving a minimax linear fractional programming problem (MLFP), which has a wide range of applications in data envelopment analysis, engineering optimization, management optimization, and so on. In this algorithm, by introducing auxiliary variables, we first equivalently transform the problem (MLFP) into the problem (EP). By using a new linear relaxation technique, the problem (EP) is reduced to a sequence of linear relaxation problems over the outer space rectangle, which provides the valid lower bound for the optimal value of the problem (EP). Based on the outer space branch-and-bound search and the linear relaxation problem, an outer space branch-and-bound algorithm is constructed for globally solving the problem (MLFP). In addition, the convergence and complexity of the presented algorithm are given. Finally, numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an efficient branch-and-bound algorithm for globally solving a class of fractional programming problems, which are widely used in communication engineering, financial engineering, portfolio optimization, and other fields. Since the kind of fractional programming problems is nonconvex, in which multiple locally optimal solutions generally exist that are not globally optimal, so there are some vital theoretical and computational difficulties. In this paper, first of all, for constructing this algorithm, we propose a novel linearizing method so that the initial fractional programming problem can be converted into a linear relaxation programming problem by utilizing the linearizing method. Secondly, based on the linear relaxation programming problem, a novel branch-and-bound algorithm is designed for the kind of fractional programming problems, the global convergence of the algorithm is proved, and the computational complexity of the algorithm is analysed. Finally, numerical results are reported to indicate the feasibility and effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]