Search Advanced

AIMS Mathematics

2024, Volume 9, Issue 6: 16376-16391. doi: 10.3934/math.2024793
Previous Article Next Article
Research article

Global optimization algorithm for a class of linear ratios optimization problem

  • 1.
    School of Mathematics and Statistics, Nanyang Normal University, Nanyang 473061, China
  • 2.
    School of Mathematics and Statistics, Henan University, Kaifeng 475004, China
  • 3.
    Center for Applied Mathematics of Henan Province, Henan University, Zhengzhou 450046, China
  • 4.
    School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China
  • Received: 31 December 2023 Revised: 26 March 2024 Accepted: 17 April 2024 Published: 09 May 2024

  • MSC : 90C26, 90C32

  • We presented an image space branch-and-bound algorithm for globally minimizing the sum of linear ratios problem. In the algorithm, a new linearizing technique was proposed for deriving the linear relaxation problem. An image space region reduction technique was constructed for improving the convergence speed of the algorithm. Moreover, by analyzing the computational complexity of the algorithm, the maximum iterations of the algorithm were estimated, and numerical experimental results showed the potential computing benefits of the algorithm. Finally, a practical application problem in education investment was solved to verify the usefulness of the proposed algorithm.

    Citation: Hongwu Li, Longfei Wang, Yingfeng Zhao. Global optimization algorithm for a class of linear ratios optimization problem[J]. AIMS Mathematics, 2024, 9(6): 16376-16391. doi: 10.3934/math.2024793

    Related Papers:

  • We presented an image space branch-and-bound algorithm for globally minimizing the sum of linear ratios problem. In the algorithm, a new linearizing technique was proposed for deriving the linear relaxation problem. An image space region reduction technique was constructed for improving the convergence speed of the algorithm. Moreover, by analyzing the computational complexity of the algorithm, the maximum iterations of the algorithm were estimated, and numerical experimental results showed the potential computing benefits of the algorithm. Finally, a practical application problem in education investment was solved to verify the usefulness of the proposed algorithm.


    加载中


    [1] I. M. Stancu-Minasian, Fractional programming: Theory, methods and applications, Springer Science & Business Media, 1997. https://doi.org/10.1007/978-94-009-0035-6
    [2] E. B. Bajalinov, Linear-fractional programming theory, methods, applications and software, Boston: Kluwer Academic Publishers, 2003. https://doi.org/10.1007/978-1-4419-9174-4
    [3] I. M. Stancu-Minasian, A ninth bibliography of fractional programming, Optimization, 68 (2019), 2125–2169. https://doi.org/10.1080/02331939908844438 doi: 10.1080/02331939908844438
    [4] H. Konno, Y. Yajima, T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Glob. Optim., 1 (1991), 65–81. https://doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
    [5] A. Cambini, L. Martein, S. Schaible, On maximizing a sum of ratios, J. Inform. Optim. Sci., 10 (1989), 65–79. https://doi.org/10.1080/02522667.1989.10698952 doi: 10.1080/02522667.1989.10698952
    [6] 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
    [7] 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
    [8] 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
    [9] Y. Ji, K. C. Zhang, S. J. Qu, A deterministic global optimization algorithm, Appl. Math. Comput., 185 (2007), 382–387. https://doi.org/10.1016/j.amc.2006.06.101 doi: 10.1016/j.amc.2006.06.101
    [10] 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
    [11] 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
    [12] 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
    [13] 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
    [14] H. W. Jiao, J. Q. Ma, P. P. Shen, Y. J. 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
    [15] B. D. Huang, P. P. Shen, An efficient branch and bound reduction algorithm for globally solving linear fractional programming problems, Chaos Soliton. Fract., 182 (2024), 114757. https://doi.org/10.1016/j.chaos.2024.114757 doi: 10.1016/j.chaos.2024.114757
    [16] P. P. Shen, Y. F. Wang, D. X. 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
    [17] H. W. Jiao, Y. D. Sun, W. J. Wang, Y. L. Shang, Global algorithm for effectively solving min-max affine fractional programs, J. Appl. Math. Comput., 70 (2024), 1787–1811. https://doi.org/10.1007/s12190-024-02027-1 doi: 10.1007/s12190-024-02027-1
    [18] H. W. Jiao, W. J. Wang, Y. L. Shang, Outer space branch-reduction-bound algorithm for solving generalized affine multiplicative problem, J. Comput. Appl. Math., 419 (2023), 114784. https://doi.org/10.1016/j.cam.2022.114784 doi: 10.1016/j.cam.2022.114784
    [19] H. W. Jiao, J. Q. Ma, Optimizing generalized linear fractional program using the image space branch-reduction-bound scheme, Optimization, 2024, 1–32. https://doi.org/10.1080/02331934.2023.2253816
    [20] 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
    [21] H. W. Jiao, B. B. Li, W. Q. Yang, A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems, J. Glob. Optim., 2024. https://doi.org/10.1007/s10898-023-01358-w
    [22] 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
    [23] Y. Ji, Y. Y. Li, C. Wijekoon, Robust two-stage minimum asymmetric cost consensus models under uncertainty circumstances, Inform. Sciences, 663 (2024), 120279. https://doi.org/10.1016/j.ins.2024.120279 doi: 10.1016/j.ins.2024.120279
    [24] Y. Ji, Y. F. Ma, The robust maximum expert consensus model with risk aversion, Inform. Fusion, 99 (2023), 101866. https://doi.org/10.1016/j.inffus.2023.101866 doi: 10.1016/j.inffus.2023.101866
    [25] 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
  • Reader Comments
  • © 2024 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.4

Metrics

Article views(470) PDF downloads(48) Cited by(2)

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