Search Advanced

AIMS Mathematics

2025, Volume 10, Issue 9: 20843-20861. doi: 10.3934/math.2025931
Previous Article Next Article
Research article

Global algorithm for addressing sum of linear ratios problem using the separable nature of relaxation problem

  • 1.
    School of Statistics and Mathematics, Henan Finance University, Zhengzhou 450046, China
  • 2.
    School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China
  • 3.
    College of Information Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450000, China
  • Published: 10 September 2025

  • MSC : 65K05, 90C26, 90C32

  • This paper proposed an algorithm based on the branch-and-bound framework for globally solving the sum of linear ratios problem (SLRP) with a large number of ratios and a small number of variables. First, we introduced new variables to construct an equivalent problem of the problem (SLRP). Then, using a new linear relaxation technique, we obtained the linear relaxation problem for the equivalent problem. By utilizing the separable nature of the linear relaxation problem, we computed the linear relaxation problem by solving its $ p $ linear programming subproblems, thereby the lower bound for the problem (SLRP) could be obtained. Additionally, we conducted a theoretical analysis of the proposed algorithm and validated its feasibility and effectiveness through numerical experiments.

    Citation: Qunzhen Zheng, Chenglin He, Yan Shi, Jingben Yin. Global algorithm for addressing sum of linear ratios problem using the separable nature of relaxation problem[J]. AIMS Mathematics, 2025, 10(9): 20843-20861. doi: 10.3934/math.2025931

    Related Papers:

  • This paper proposed an algorithm based on the branch-and-bound framework for globally solving the sum of linear ratios problem (SLRP) with a large number of ratios and a small number of variables. First, we introduced new variables to construct an equivalent problem of the problem (SLRP). Then, using a new linear relaxation technique, we obtained the linear relaxation problem for the equivalent problem. By utilizing the separable nature of the linear relaxation problem, we computed the linear relaxation problem by solving its $ p $ linear programming subproblems, thereby the lower bound for the problem (SLRP) could be obtained. Additionally, we conducted a theoretical analysis of the proposed algorithm and validated its feasibility and effectiveness through numerical experiments.



    加载中


    [1] E. Arkin, Y. Chiang, M. Held, J. Mitchell, V. Sacristan, S. Skiena, et al., On minimum-area hulls, Algorithmica, 21 (1998), 119–136. https://doi.org/10.1007/PL00009204
    [2] E. B. Bajalinov, Linear-fractional programming theory, methods, applications and software, Dordrecht: Kluwer Academic Publishers, 2003. https://doi.org/10.1007/978-1-4419-9174-4
    [3] H. P. Benson, Vector maximization with two objective functions, J. Optim. Theory Appl., 28 (1979), 253–257. https://doi.org/10.1007/BF00933245 doi: 10.1007/BF00933245
    [4] 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
    [5] M. Borza, A. S. Rambely, A linearization to the sum of linear ratios programming problem, Mathematics, 9 (2021), 1004. https://doi.org/10.3390/math9091004 doi: 10.3390/math9091004
    [6] A. Charnes, W. W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9 (1962), 181–186. https://doi.org/10.1002/nav.3800090303 doi: 10.1002/nav.3800090303
    [7] C. S. Colantoni, R. P. Manes, A. Whinston, Programming, profit rates and pricing decisions, Account. Rev., 44 (1969), 467–481.
    [8] D. F. Dennis, Analyzing public inputs to multiple objective decisions on national forests using conjoint analysis, Forest Sci., 44 (1998), 421–429. https://doi.org/10.1093/forestscience/44.3.421 doi: 10.1093/forestscience/44.3.421
    [9] J. E. Falk, S. W. Palocsay, Optimizing the sum of linear fractional functions, In: Recent advances in global optimization, Princeton: Princeton University Press, 1991,221–258. https://doi.org/10.1515/9781400862528.221
    [10] Z. Hou, S. Liu, An efficient image space branch-reduction-bound algorithm to globally solve generalized fractional programming problems for large-scale real applications, J. Comput. Appl. Math., 451 (2024), 116070. https://doi.org/10.1016/j.cam.2024.116070 doi: 10.1016/j.cam.2024.116070
    [11] Z. Hou, S. 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
    [12] Z. Hou, S. 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
    [13] H. Jiao, S. 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. Jiao, S. Liu, Y. Zhao, Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Appl. Math. Model., 39 (2015), 7568–7582. https://doi.org/10.1016/j.apm.2015.03.025 doi: 10.1016/j.apm.2015.03.025
    [15] H. Jiao, B. Li, Y. 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
    [16] H. Jiao, J. Ma, P. Shen, Y. Qiu, Effective algorithm and computational complexity for solving sum of linear ratios problem, J. Ind. Manag. Optim., 19 (2023), 4410–4427. https://doi.org/10.3934/jimo.2022135 doi: 10.3934/jimo.2022135
    [17] H. Jiao, J. Ma, An efficient algorithm and complexity result for solving the sum of general ratios problem, Chaos Soliton. Fract., 164 (2022), 112701. https://doi.org/10.1016/j.chaos.2022.112701 doi: 10.1016/j.chaos.2022.112701
    [18] H. Jiao, Y. Shang, R. 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
    [19] H. Jiao, Y. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc., 11 (2023), 569–594. https://doi.org/10.1007/s40305-021-00375-4 doi: 10.1007/s40305-021-00375-4
    [20] H. Jiao, Y. Shang, W. 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
    [21] H. Jiao, B. Li, W. 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
    [22] H. Jiao, J. 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
    [23] H. Jiao, J. Ma, Y. 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
    [24] H. Jiao, Y. Shang, Image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem, J. Comput. Math., 43 (2025), 203–228. https://doi.org/10.4208/jcm.2203-m2021-0085 doi: 10.4208/jcm.2203-m2021-0085
    [25] H. Konno, M. Inori, Bond portfolio optimization by bilinear fractional programming, J. Oper. Res. Soc. Jpn., 32 (1989), 143–158. https://doi.org/10.15807/jorsj.32.143 doi: 10.15807/jorsj.32.143
    [26] H. Li, L. Wang, Y. Zhao, Global optimization algorithm for a class of linear ratios optimization problem, AIMS Mathematics, 9 (2024), 16376–16391. https://doi.org/10.3934/math.2024793 doi: 10.3934/math.2024793
    [27] H. Li, Y. Feng, H. Jiao, Y. 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
    [28] T. Matsui, NP-hardness of linear multiplicative programming and related problems, J. Glob. Optim., 9 (1996), 113–119. https://doi.org/10.1007/BF00121658 doi: 10.1007/BF00121658
    [29] N. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Global Optim., 26 (2003), 229–259. https://doi.org/10.1023/A:1023274721632 doi: 10.1023/A:1023274721632
    [30] P. Shen, Y. Wang, D. Wu, A spatial branch and bound algorithm for solving the sum of linear ratios optimization problem, Numer. Algor., 93 (2023), 1373–1400. https://doi.org/10.1007/s11075-022-01471-z doi: 10.1007/s11075-022-01471-z
    [31] S. Schaible, Fractional programming, In: Handbook of global optimization, Boston: Springer, 1995,495–608. https://doi.org/10.1007/978-1-4615-2025-2_10
    [32] 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
    [33] I. M. Stancu-Minasian, A ninth bibliography of fractional programming, Optimization, 68 (2019), 2125–2169. https://doi.org/10.1080/02331934.2019.1632250 doi: 10.1080/02331934.2019.1632250
    [34] I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), 439–470. https://doi.org/10.1080/02331934.2016.1276179 doi: 10.1080/02331934.2016.1276179
    [35] A. Q. Tian, H. X. Lv, X. Y. Wang, J. S. Pan, V. Sn$\acute{a}\check{s}$el, Bioinspired discrete two-stage surrogate-assisted algorithm for large-scale traveling salesman problem, J. Bionic. Eng., 22 (2025), 1926–1939. https://doi.org/10.1007/s42235-025-00724-6 doi: 10.1007/s42235-025-00724-6
    [36] A. Q. Tian, F. F. Liu, H. X. Lv, Snow Geese algorithm: a novel migration-inspired meta-heuristic algorithm for constrained engineering optimization problems, Appl. Math. Model., 126 (2024), 327–347. https://doi.org/10.1016/j.apm.2023.10.045 doi: 10.1016/j.apm.2023.10.045
    [37] D. Zhan, A. Q. Tian, S. Q. Ni, Optimizing PID control for multi-model adaptive high-speed rail platform door systems with an improved metaheuristic approach, Int. J. Elec. Power., 169 (2025), 110738. https://doi.org/10.1016/j.ijepes.2025.110738 doi: 10.1016/j.ijepes.2025.110738
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.1

Metrics

Article views(466) PDF downloads(33) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog