Search

This paper aims to globally solve a generalized affine fractional program problem (GAFPP). Firstly, by introducing some outer space variables and performing equivalent transformations, we can derive the equivalence problem (EP) of the GAFPP. Secondly, by constructing a novel linear relaxation method, we can deduce the affine relaxation problem (ARP) of the EP. Next, by solving the ARP to compute the lower bound, we propose a new outer space branch-and-bound algorithm for tackling the GAFPP. Then, the global convergence of the algorithm is proved, and the computational complexity of the algorithm in the worst case is analyzed. Finally, numerical experimental results are reported to illustrate the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

This article presents and validates a potential practical algorithm for minimizing the sum of affine fractional functions over a polyhedron. During the branch and bound search, this algorithm computes the lower bounds by solving the affine relaxation problems of the equivalent problem, which are derived by utilizing a two-level affine relaxation technique. By successive refinement and successively solving a series of affine relaxation problems, the algorithm is convergent to the global minimum of the primal problem. Moreover, the gap between the objective function and its affine relaxation function is derived for the first time, and when the partition interval tends to be infinitesimal, the gap is infinitely close to zero. Furthermore, the maximum iterations of the proposed algorithm are derived by estimating its computational complexity. Some test problems are solved to verify the potential practical and computational advantages of the algorithm. [ABSTRACT FROM AUTHOR]

This paper presents an effective algorithm for globally solving the sum of linear ratios problem (SLRP), which has broad applications in government planning, finance and investment, cluster analysis, game theory and so on. In this paper, by using a new linearization technique, the linear relaxation problem of the equivalent problem is constructed. Next, based on the linear relaxation problem and the branch-and-bound framework, an effective branch-and-bound algorithm for globally solving the problem (SLRP) is proposed. By analyzing the computational complexity of the proposed algorithm, the maximum number of iterations of the algorithm is derived. Numerical experiments are reported to verify the effectiveness and feasibility of the proposed algorithm. Finally, two practical application problems from power transportation and production planning are solved to verify the feasibility of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider the min–max linear fractional programming problem (MLFP) which is NP-hard. We first introduce some auxiliary variables to derive an equivalent problem of the problem (MLFP). An outer space branch-and-bound algorithm is then designed by integrating some basic operations such as the linear relaxation method and branching rule. The global convergence of the proposed algorithm is proved by means of the subsequent solutions of a series of linear relaxation programming problems, and the computational complexity of the proposed algorithm is estimated based on the branching rule. Finally, numerical experimental results demonstrate the proposed algorithm can be used to efficiently compute the globally optimal solutions of test examples. [ABSTRACT FROM AUTHOR]

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]