Efficient algorithm for addressing large-scale linear fractional program problems

Zhiguo Ge; Hongwei Jiao; Zhiguo Ge; Hongwei Jiao

doi:10.3934/math.2025938

AIMS Mathematics

2025, Volume 10, Issue 9: 21004-21024. doi: 10.3934/math.2025938

Previous Article Next Article

Research article

Efficient algorithm for addressing large-scale linear fractional program problems

Zhiguo Ge ^{1
,
,},
Hongwei Jiao ^{2
,
,}

1.
Innovation and Entrepreneurship College, Henan Medical University, Xinxiang 453003, China
2.
School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China

Received: 30 June 2025 Revised: 28 August 2025 Accepted: 02 September 2025 Published: 12 September 2025
MSC : 65K05, 90C26, 90C32

This paper presented an efficient algorithm for addressing large-scale linear fractional program problems, which are widely used in hospital management. First of all, we converted the initial problem into an equivalent problem by applying the Charnes-Cooper transformation technique. Next, by directly relaxing the nonlinear constraints, a mixed-integer linear relaxation problem was then constructed. Subsequently, by successively partitioning the initial output space rectangle and solving a series of mixed-integer linear relaxation problems, we proposed an efficient branch-relaxation-bound algorithm for globally addressing large-scale linear fractional program problems for the first time. Moreover, the computation complexity of the algorithm was analyzed, and the maximum number of iterations of the algorithm in the worst-case scenario was estimated. Furthermore, the experimental results demonstrated the high efficiency of the proposed algorithm in solving the investigated large-scale linear fractional program problem.
- large-scale linear fractional program,
- global optimization,
- branch-and-bound algorithm,
- computation complexity
Citation: Zhiguo Ge, Hongwei Jiao. Efficient algorithm for addressing large-scale linear fractional program problems[J]. AIMS Mathematics, 2025, 10(9): 21004-21024. doi: 10.3934/math.2025938

Related Papers:

Abstract

This paper presented an efficient algorithm for addressing large-scale linear fractional program problems, which are widely used in hospital management. First of all, we converted the initial problem into an equivalent problem by applying the Charnes-Cooper transformation technique. Next, by directly relaxing the nonlinear constraints, a mixed-integer linear relaxation problem was then constructed. Subsequently, by successively partitioning the initial output space rectangle and solving a series of mixed-integer linear relaxation problems, we proposed an efficient branch-relaxation-bound algorithm for globally addressing large-scale linear fractional program problems for the first time. Moreover, the computation complexity of the algorithm was analyzed, and the maximum number of iterations of the algorithm in the worst-case scenario was estimated. Furthermore, the experimental results demonstrated the high efficiency of the proposed algorithm in solving the investigated large-scale linear fractional program problem.

References

[1]	E. B. Bajalinov, Linear-fractional programming theory, methods, applications and software, New York: Springer, 2003. http://doi.org/10.1007/978-1-4419-9174-4
[2]	H. P. Benson, Global optimization algorithm for the nonlinear sum of ratios problem, J. Optim. Theory Appl., 112 (2002), 1–29. https://doi.org/10.1023/A:1013072027218 doi: 10.1023/A:1013072027218
[3]	H. P. Benson, A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, Eur. J. Oper. Res., 182 (2007), 597–611. https://doi.org/10.1016/j.ejor.2006.08.036 doi: 10.1016/j.ejor.2006.08.036
[4]	H. P. Benson, Branch-and-bound outer approximation algorithm for sum-of-ratios fractional programs, J. Optim. Theory Appl., 146 (2010), 1–18. https://doi.org/10.1007/s10957-010-9647-8 doi: 10.1007/s10957-010-9647-8
[5]	H. P. Benson, Using concave envelopes to globally solve the nonlinear sum of ratios problem, J. Glob. Optim., 22 (2002), 343–364. https://doi.org/10.1023/A:1013869015288 doi: 10.1023/A:1013869015288
[6]	J. G. Carlsson, J. M. Shi, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Oper. Res. Lett., 41 (2013), 381–389. https://doi.org/10.1016/j.orl.2013.04.005 doi: 10.1016/j.orl.2013.04.005
[7]	Y. Chaiblaine, M. Moulaï, An exact method for solving the integer sum of linear ratios problem, Optimization, 73 (2024), 461–479. https://doi.org/10.1080/02331934.2022.2112190 doi: 10.1080/02331934.2022.2112190
[8]	M. C. Dorneich, N. V. Sahinidis, Global optimization algorithms for chip layout and compaction, Eng. Optimiz., 25 (1995), 131–154. https://doi.org/10.1080/03052159508941259 doi: 10.1080/03052159508941259
[9]	J. E. Falk, S. W. Palocsay, Image space analysis of generalized fractional programs, J. Glob. Optim., 4 (1994), 63–88. https://doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
[10]	R. W. Freund, F. Jarre, Solving the sum-of-ratios problem by an interior-point method, J. Glob. Optim., 19 (2001), 83–102. https://doi.org/10.1023/A:1008316327038 doi: 10.1023/A:1008316327038
[11]	Y. L. Gao, S. Q. Jin, A global optimization algorithm for sum of linear ratios problem, J. Appl. Math., 2013 (2013), 276245. https://doi.org/10.1155/2013/276245 doi: 10.1155/2013/276245
[12]	H. W. Jiao, B. B. Li, Y. L. Shang, An outer space approach to tackle generalized affine fractional program problems, J. Optim. Theory Appl., 201 (2024), 1–35. https://doi.org/10.1007/s10957-023-02368-0 doi: 10.1007/s10957-023-02368-0
[13]	H. W. Jiao, S.-Y. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243 (2015), 723–730. https://doi.org/10.1016/j.ejor.2015.01.039 doi: 10.1016/j.ejor.2015.01.039
[14]	H. W. Jiao, S. Y. Liu, J. B. Yin, Y. F. Zhao, Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 14 (2016), 736–746. https://doi.org/10.1515/math-2016-0058 doi: 10.1515/math-2016-0058
[15]	H. W. Jiao, Y. L. Shang, R. J. Chen, A potential practical algorithm for minimizing the sum of affine fractional functions, Optimization, 72 (2023), 1577–1607. https://doi.org/10.1080/02331934.2022.2032051 doi: 10.1080/02331934.2022.2032051
[16]	H. W. Jiao, Y. L. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc. China, 11 (2023), 569–594. https://doi.org/10.1007/s40305-021-00375-4 doi: 10.1007/s40305-021-00375-4
[17]	H. W. Jiao, Y. L. Shang, W. J. Wang Solving generalized polynomial problem by using new affine relaxed technique, Int. J. Comput. Math., 99 (2022), 309–331. https://doi.org/10.1080/00207160.2021.1909727 doi: 10.1080/00207160.2021.1909727
[18]	E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, B. Dilkina, Learning to branch in mixed integer programming, Proceedings of the AAAI conference on artificial intelligence, 30 (2016). https://doi.org/10.1609/aaai.v30i1.10080
[19]	A. Khajavirad, N. V. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Prog. Comp., 10 (2018), 383–421. https://doi.org/10.1007/s12532-018-0138-5 doi: 10.1007/s12532-018-0138-5
[20]	A. A. Khan, R. S. Adve, W. Yu, Optimizing downlink resource allocation in multiuser MIMO networks via fractional programming and the hungarian algorithm, IEEE T. Wirel. Commun., 19 (2020), 5162–5175. https://doi.org/10.1109/TWC.2020.2990176 doi: 10.1109/TWC.2020.2990176
[21]	H. Konno, H. Watanabe, Bond portfolio optimization problems and their applications to index tracking: A partial optimization approach, J. Oper. Res. Soc. Jpn., 39 (1996), 295–306. https://doi.org/10.15807/jorsj.39.295 doi: 10.15807/jorsj.39.295
[22]	T. Kuno, A branch-and-bound algorithm for maximizing the sum of several linear ratios, J. Glob. Optim., 22 (2002), 155–174. https://doi.org/10.1023/A:1013807129844 doi: 10.1023/A:1013807129844
[23]	N. T. H. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26 (2003), 229–259. https://doi.org/10.1023/A:1023274721632 doi: 10.1023/A:1023274721632
[24]	P. P. Shen, C. F. Wang, Global optimization for sum of linear ratios problem with coefficients, Appl. Math. Comput., 176 (2006), 219–229. https://doi.org/10.1016/j.amc.2005.09.047 doi: 10.1016/j.amc.2005.09.047
[25]	P. P. Shen, T. Lu, Regional division and reduction algorithm for minimizing the sum of linear fractional functions, J. Inequal. Appl., 2018 (2018), 63. https://doi.org/10.1186/s13660-018-1651-9 doi: 10.1186/s13660-018-1651-9
[26]	P. P. Shen, B. D. Huang, L. F. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324–342. https://doi.org/10.1016/j.cam.2018.10.038 doi: 10.1016/j.cam.2018.10.038
[27]	Y. H. Shi, Global optimization for sum-of-ratios problems, Master Thesis, Henan Normal University, 2011.
[28]	I. M. Stancu-Minasian, Fractional programming: theory, methods and applications, Dordrecht: Springer, 1997. https://doi.org/10.1007/978-94-009-0035-6
[29]	J. P. Vielma, S. Ahmed, G. Nemhauser, Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Oper. Res., 58 (2009), 303–315. https://doi.org/10.1287/opre.1090.0721 doi: 10.1287/opre.1090.0721
[30]	L. A. Wolsey, Mixed integer programming, In: Wiley encyclopedia of computer science and engineering, New York: Wiley, 2008. https://doi.org/10.1002/9780470050118.ecse244
[31]	B. Zhang, Y. L. Gao, X. Liu, X. L. Huang, A new deterministic global computing algorithm for solving a kind of linear fractional programming, Optimization, 72 (2023), 1485–1513. https://doi.org/10.1080/02331934.2022.2027940 doi: 10.1080/02331934.2022.2027940
[32]	X. F. Zhang, R. Liu, J. X. Ren, Q. L. Gui, Adaptive fractional image enhancement algorithm based on rough set and particle swarm optimization, Fractal Fract., 6 (2022), 100. https://doi.org/10.3390/fractalfract6020100 doi: 10.3390/fractalfract6020100
[33]	J.-X. Zhang, G.-H. Yang, Low-complexity tracking control of strict-feedback systems with unknown control directions, IEEE T. Automat. Contr., 64 (2019), 5175–5182. https://doi.org/10.1109/TAC.2019.2910738 doi: 10.1109/TAC.2019.2910738
[34]	J.-X. Zhang, Y.-Q. Liu, T. Y. Chai, Singularity-free low-complexity fault-tolerant prescribed performance control for spacecraft attitude stabilization, IEEE T. Autom. Sci. Eng., 22 (2025), 15408–15419. https://doi.org/10.1109/TASE.2025.3569566 doi: 10.1109/TASE.2025.3569566
[35]	F. H. Mathis, L. J. Mathis, A nonlinear programming algorithm for hospital management, SIAM Rev., 37 (1995), 230–234. https://doi.org/10.1137/1037046 doi: 10.1137/1037046
[36]	H. W. Li, L. F. Wang, Y. F. Zhao, Global optimization algorithm for a class of linear ratios AIMS Mathematics, 9 (2024), 16376–16391. https://doi.org/10.3934/math.2024793
[37]	H. W. Li, Y. F. Feng, H. W. Jiao, Y. L. Shang, A novel algorithm for solving sum of several affine fractional functions, AIMS Mathematics, 8 (2023), 9247–9264. https://doi.org/10.3934/math.2023464 doi: 10.3934/math.2023464
[38]	Z. S. Hou, S. Y. Liu, An efficient image space branch-reduction-bound algorithm to globally solve generalized fractional programming problems for J. Comput. Appl. Math., 451 (2024), 116070. https://doi.org/10.1016/j.cam.2024.116070
[39]	Z. S. Hou, S. Y. Liu, A spatial branch-reduction-bound algorithm for solving generalized linear fractional problems globally, Chaos Soliton. Fract., 176 (2023), 114144. https://doi.org/10.1016/j.chaos.2023.114144 doi: 10.1016/j.chaos.2023.114144
[40]	Z. S. Hou, S. Y. Liu, An accelerating outer space algorithm for globally solving generalized linear multiplicative problems, Numer. Algor., 94 (2023), 877–904. https://doi.org/10.1007/s11075-023-01523-y doi: 10.1007/s11075-023-01523-y
[41]	H. W. Jiao, B. B. Li, W. Q. Yang, A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems, J. Glob. Optim., 89 (2024), 597–632. https://doi.org/10.1007/s10898-023-01358-w doi: 10.1007/s10898-023-01358-w
[42]	H. W. Jiao, J. Q. Ma, Optimizing generalized linear fractional program using the image space branch-reduction-bound scheme, Optimization, 74 (2025), 1–32. https://doi.org/10.1080/02331934.2023.2253816 doi: 10.1080/02331934.2023.2253816
[43]	H. W. Jiao, J. Q. Ma, Y. L. Shang, Reduced outer space algorithm for globally computing affine sum-of-ratios problems, Asia Pac. J. Oper. Res., 42 (2025), 2450015. https://doi.org/10.1142/S0217595924500155 doi: 10.1142/S0217595924500155

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)