Search

In this paper, we present a range division and compression algorithm for effectively solving quadratically constrained sum of quadratic ratios problem. In this algorithm, a novel linear relaxation approach is proposed for deriving linear relaxation programming, which is used to obtain a lower bound of the optimal value of this problem. By utilizing the known upper bound and the constructed linear relaxation programming, a range compression technique is presented to contract the investigated range. Thus, a range division and compression algorithm is constructed and its convergence is proved. Compared with the current approaches, the proposed algorithm does not need to introduce new variables and constraints and it does not need to employ additional procedure to calculate the intervals of numerator and denominator of each ratio, so that this will facilitate the implementation of this algorithm. Finally, numerical comparisons with the known algorithms demonstrate the advantage of the proposed algorithm. [ABSTRACT FROM AUTHOR]

For globally solving sum of linear ratios problem (SLRP), this paper presents a new branch-and-bound method. In this method, a new linear relaxation technique is proposed firstly; then, the initial problem SLRP is solved by a sequence of linear programming problems. Meanwhile, to improve the convergence speed of our algorithm, two accelerating techniques are presented. The proposed algorithm is proved to be convergent, and some experiments are provided to show its feasibility and efficiency. [ABSTRACT FROM AUTHOR]

In this paper, for solving generalized linear fractional programming (GLFP), a new branch-and-reduce approach is presented. Firstly, an equivalent problem (EP) of GLFP is given; then, a new linear relaxation technique is proposed; finally, the problem EP is reduced to a sequence of linear programming problems by using the new linear relaxation technique. Meanwhile, to improve the convergence speed of our algorithm, two reducing techniques are presented. The proposed algorithm is proved to be convergent, and some experiments are provided to show its feasibility and efficiency. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm. [Copyright &y& Elsevier]

Deterministic branch and bound methods for the solution of general nonlinear programs have become increasingly popular during the last decade or two, with increasing computer speed, algorithmic improvements, and multiprocessors. Presently, there are several commercial packages. Although such packages are based on exhaustive search, not all of them rigorously take account of roundoff error, singularities, and other possibilities. Popular non-rigorous packages have much in common with mathematically rigorous packages, including overall structure and basic techniques. Nonetheless, it is not trivial to make non-rigorous packages rigorous. We define different kinds of answers that global optimization software can claim to provide, explain where rigour might be needed and where it is not practical, briefly review salient techniques common to deterministic branch and bound methods, illustrate pitfalls in non-rigorous branch and bound methods, outline some of the techniques to make non-rigorous software rigorous, and provide guidance for research into and implementation of these techniques, provide some theoretical backing, with examples, for convergence of common relaxation techniques. [ABSTRACT FROM AUTHOR]