Search

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 article presents and validates a new branch-and-bound algorithm for effectively solving the generalized polynomial problem (GPP). In this algorithm, a new affine relaxed technique is derived for establishing the relaxed linear programs problem of the GPP. In addition, some box reducing manipulations are employed to improve the speed of branch-and-bound search of the algorithm. Combining the relaxed linear programs problem with the box reducing manipulations, a new branch-and-bound algorithm is constructed. Some numerical examples are solved to verify the potential practical and computing advantages of the algorithm. At last, several engineering design problems are solved to validate the usefulness of the algorithm. [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]

In this article, we present a parametric linear relaxation algorithm for globally solving the nonconvex quadratic programming (NQP). In this algorithm, a new parametric linearized technique is proposed for generating parametric linear relaxation programming (PLRP) of the NQP, which can be used to determine the lower bound of global minimum value of the NQP. To improve the convergent speed of the proposed algorithm, a pruning operation is employed to compress the investigated region. By subdividing subsequently the initial domain and solving subsequently a series of parametric linear relaxation programming problems over the subdivided domain, the proposed algorithm is convergent to the global minimum of the NQP. Finally, an engineering problem for the design of heat exchanger network and some test examples are used to verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]