Volume 57, Number 3, May-June 2023
|Page(s)||1523 - 1537|
|Published online||21 June 2023|
Efficient algorithm for globally computing the min–max linear fractional programming problem
School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, P.R. China
2 School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, P.R. China
3 School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, P.R. China
* Corresponding author: firstname.lastname@example.org
Accepted: 30 May 2023
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.
Mathematics Subject Classification: 90C32 / 90C26
Key words: Min–max linear fractional programming / global optimization / linear relaxation problem / branch-and-bound / computational complexity
© The authors. Published by EDP Sciences, ROADEF, SMAI 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.