Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

WANG Hui-man, SHEN Pei-ping, LIANG Yu-xin

doi:10.13371/j.cnki.chin.q.j.m.2024.04.005

Chinese Quarterly Journal of Mathematics >

2024 , Vol. 39 >Issue 4: 388 - 398

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2024.04.005

Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

Expand

School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China

WANG Hui-man (1999-), female, native of Hebi, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application; SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; LIANG Yu-xin (2000-), female, native of Nanyang, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application.

Received date: 2024-02-27

Online published: 2024-12-30

Supported by

Supported by the National Natural Science Foundation of China (Grant Nos. 12071133 and 11871196).

Fold

Abstract

In this paper, we study the minimax linear fractional programming problem on a non-empty bounded set, called problem (MLFP), and we design a branch and bound algorithm to find a globally optimal solution of (MLFP). Firstly, we convert the problem (MLFP) to a problem (EP2) that is equivalent to it. Secondly, by applying the convex relaxation technique to problem (EP2), a convex quadratic relaxation problem (CQRP) is obtained. Then, the overall framework of the algorithm is given and its convergence is proved, the worst-case iteration number is also estimated. Finally, experimental data are
listed to illustrate the effectiveness of the algorithm.

Key words： Minimax linear fractional programming; Global optimal solution; Branch and bound

Cite this article

WANG Hui-man, SHEN Pei-ping, LIANG Yu-xin . Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming[J]. Chinese Quarterly Journal of Mathematics, 2024 , 39(4) : 388 -398 . DOI: 10.13371/j.cnki.chin.q.j.m.2024.04.005

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article