1. An efficient algorithm and complexity result for solving the sum of general affine ratios problem.
- Author
-
Jiao, Hongwei and Ma, Junqiao
- Subjects
- *
OUTER space , *RUNNING speed , *ALGORITHMS , *TRANSPORTATION planning , *LINEAR programming , *RECTANGLES - Abstract
In this paper, with the unique hypothesis that the denominator is not equal to 0, an efficient outer space rectangle branch-and-bound algorithm is presented to globally solve the sum of general affine ratios problem. By using equivalent transformation and the characteristics of general single ratio function, a linear program relaxation problem is constructed for computing the lower bound of the global minimum value of the original problem. Moreover, to enhance the running speed of the presented algorithm, we design an outer space accelerating technic for deleting the entire outer space rectangle or a part of the entire examined outer space rectangle, in which there contains no the global minimum point of the equivalent problem. Furthermore, through the complexity analysis of the presented algorithm, we estimate its maximum iteration times. In addition, we prove the global convergence of the presented algorithm, report and analyze the numerical computational results for indicating the validity of the presented algorithm. Finally, two practical problems from power transportation and production planning are solved to verify the usefulness of the presented algorithm. • We present a novel outer space branch-and-bound algorithm for the SGAR. • The algorithm economizes the required computations by dividing space. • The main calculation involves solving a series of linear programming problems. • We give the complexity analysis of the algorithm for the first time. • The computing efficiency is significantly higher than the existing algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF