An efficient algorithm and complexity result for solving the sum of general affine ratios problem

Hongwei Jiao and Junqiao Ma

Chaos, Solitons & Fractals, 2022, vol. 164, issue C

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.

Keywords: Sum of general affine ratios; Complexity analysis; Global optimization; Branch-and-bound; Accelerating technic (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077922008803
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:164:y:2022:i:c:s0960077922008803

DOI: 10.1016/j.chaos.2022.112701

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().