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
² School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, P.R. China
³ School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, P.R. China

^* Corresponding author: jiaohongwei@126.com

Received: 4 July 2022
Accepted: 30 May 2023

Abstract

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.