Search Advanced

AIMS Mathematics

2024, Volume 9, Issue 9: 23837-23858. doi: 10.3934/math.20241158
Previous Article Next Article
Research article

Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem

  • 1.
    College of Information Engineering, Henan University of Animal Husbandry and Economy, Zhengzhou 450000, China; wqmshiyan@163.com
  • 2.
    School of Statistics and Mathematics, Henan Finance University, Zhengzhou 450046, China
  • 3.
    School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China
  • Received: 27 April 2024 Revised: 17 July 2024 Accepted: 29 July 2024 Published: 09 August 2024

  • MSC : 90C32, 90C26

  • This paper proposes an efficient method for acquiring the global solution of the sum of affine ratios problem (SARP) in the reduced outer space. Using equivalence conversions, the original problem was transformed into an equivalent problem. Then, an affine relaxation problem of the equivalent problem was constructed by exploiting linearization techniques. Subsequently, an outcome space branch-and-bound algorithm was proposed, the convergence of the algorithm was proved and the computational complexity was estimated. Finally, numerical examples were presented to demonstrate the effectiveness and feasibility of the presented algorithm.

    Citation: Yan Shi, Qunzhen Zheng, Jingben Yin. Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem[J]. AIMS Mathematics, 2024, 9(9): 23837-23858. doi: 10.3934/math.20241158

    Related Papers:

  • This paper proposes an efficient method for acquiring the global solution of the sum of affine ratios problem (SARP) in the reduced outer space. Using equivalence conversions, the original problem was transformed into an equivalent problem. Then, an affine relaxation problem of the equivalent problem was constructed by exploiting linearization techniques. Subsequently, an outcome space branch-and-bound algorithm was proposed, the convergence of the algorithm was proved and the computational complexity was estimated. Finally, numerical examples were presented to demonstrate the effectiveness and feasibility of the presented algorithm.



    加载中


    [1] J. Majhi, R. Janardan, J. Schwerdt, M. Smid, P. Gupta, Minimizing support structures and trapped area in two-dimensional layered manufacturing, Comput. Geom., 12 (1999), 241–267. https://doi.org/10.1016/S0925-7721(99)00003-6 doi: 10.1016/S0925-7721(99)00003-6
    [2] J. Majhi, R. Janardan, M. Smid, P. Gupta, On some geometric optimization problems in layered manufacturing, Comput. Geom., 12 (1999), 219–239. https://doi.org/10.1016/S0925-7721(99)00002-4 doi: 10.1016/S0925-7721(99)00002-4
    [3] 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
    [4] C. S. Colantoni, R. P. Manes, A. Whinston, Programming, profit rates and pricing decisions, Account. Rev., 44 (1969), 467–481.
    [5] 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
    [6] I. M. Stancu-Minasian, Fractional programming theory, methods and applications, Kluwer Academic Publishers, 1997. https://doi.org/10.1007/978-94-009-0035-6
    [7] E. B. Bajalinov, Linear-fractional programming theory, methods, applications and software, Springer Science and Business Media, 2003. https://doi.org/10.1007/978-1-4419-9174-4
    [8] 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
    [9] B. Sawik, Downside risk approach for multi-objective portfolio optimization, In: D. Klatte, L. Hans-Jakob, K. Schmedders, Operations research proceedings 2011, Springer Science and Business Media, 2012. https://doi.org/10.1007/978-3-642-29210-1_31
    [10] V. Milenkovic, K. Daniels, Z. Li, Placement and compaction of nonconvex polygons for clothing manufacture, Memorial University of Newfoundland, 1992.
    [11] E. M. Arkin, Y. J. Chiang, M. Held, J. S. B. Mitchell, V. Sacristan, S. S. Skiena, et al., On minimum-area hulls, Algorithmica, 21 (1998), 119–136. https://doi.org/10.1007/PL00009204
    [12] A. Charnes, W. W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9 (1962), 181–186. https://doi.org/10.1002/nav.3800090303 doi: 10.1002/nav.3800090303
    [13] H. Konno, Y. Yajima, T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Global Optim., 1 (1991), 65–81. https://doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
    [14] N. T. H. 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
    [15] Y. E. Nesterov, A. S. Nemirovskii, An interior-point method for generalized linear-fractional programming, Math. Program., 69 (1995), 177–204. https://doi.org/10.1007/BF01585557 doi: 10.1007/BF01585557
    [16] R. W. Freund, F. Jarre, Solving the sum-of-ratios problem by an interior-point method, J. Global Optim., 19 (2001), 83–102. https://doi.org/10.1023/A:1008316327038 doi: 10.1023/A:1008316327038
    [17] E. F. James, W. P. Susan, Image space analysis of generalized fractional programs, J. Global Optim., 4 (1994), 63–88. https://doi.org/10.1007/BF01096535 doi: 10.1007/BF01096535
    [18] T. Kuno, A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-ratios problem, J. Global Optim., 33 (2005), 215–234. https://doi.org/10.1007/s10898-004-1952-z doi: 10.1007/s10898-004-1952-z
    [19] H. Jiao, A branch and bound algorithm for globally solving a class of nonconvex programming problems, Nonlinear Anal., 70 (2009), 1113–1123. https://doi.org/10.1016/j.na.2008.02.005 doi: 10.1016/j.na.2008.02.005
    [20] K. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: theory and algorithms, John Wiley & Sons, Inc., 2006. https://doi.org/10.1002/0471787779
    [21] Y. Shi, Global optimization for sum of ratios problems, MA thesis, Henan Normal University, 2011.
    [22] H. Jiao, J. Ma, An efficient algorithm and complexity result for solving the sum of general affine ratios problem, Chaos Solitons Fract., 164 (2022), 112701. https://doi.org/10.1016/j.chaos.2022.112701 doi: 10.1016/j.chaos.2022.112701
    [23] 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
    [24] H. Jiao, J. Ma, P. Shen, Y. Qiu, Effective algorithm and computational complexity for solving sum of linear ratios problem, J. Ind. Manage. Optim., 19 (2023), 4410–4427. https://doi.org/10.3934/jimo.2022135 doi: 10.3934/jimo.2022135
    [25] H. Jiao, Y. Shang, Image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem, J. Comput. Math., 2024. https://doi.org/10.4208/jcm.2203-m2021-0085
    [26] Y. Pei, D. Zhu, Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region, J. Appl. Math. Comput., 41 (2013), 153–169. https://doi.org/10.1007/s12190-012-0602-8 doi: 10.1007/s12190-012-0602-8
    [27] T. Kuno, A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-ratios problems, J. Global Optim., 33 (2005), 215–234. https://doi.org/10.1007/s10898-004-1952-z doi: 10.1007/s10898-004-1952-z
    [28] P. P. Shen, W. M. Li, Y. C. Liang, Branch-reduction-bound algorithm for linear sum-of-ratios fractional programs, Pac. J. Optim., 11 (2015), 79–99.
    [29] H. Jiao, S. Liu, Range division and compression algorithm for quadratically constrained sum of quadratic ratios, Comput. Appl. Math., 36 (2017), 225–247. https://doi.org/10.1007/s40314-015-0224-5 doi: 10.1007/s40314-015-0224-5
    [30] H. Jiao, B. Li, W. Yang, A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems, J. Global Optim., 89 (2024), 597–632. https://doi.org/10.1007/s10898-023-01358-w doi: 10.1007/s10898-023-01358-w
    [31] 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
    [32] A. Charnes, W. W. Cooper, Programming with linear fractional functionals, Nav. Res. Log. Q., 9 (1962), 181–186. https://doi.org/10.1002/nav.3800150308 doi: 10.1002/nav.3800150308
    [33] R. Horst, H. Tuy, Global optimization, deterministic approaches, Springer-Verlag, 1990. https://doi.org/10.1007/978-3-662-02598-7
    [34] 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
    [35] P. Shen, B. Huang, L. 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
    [36] 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
    [37] 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
    [38] Y. Gao, S. Jin, A global optimization algorithm for sum of linear ratios problem, J. Appl. Math., 2013, 276245. https://doi.org/10.1155/2013/276245
    [39] 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
    [40] H. Jiao, S. Liu, J. Yin, Y. 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
    [41] H. Li, L. Wang, Y. Zhao, Global optimization algorithm for a class of linear ratios optimization problem, AIMS Math., 9 (2024), 16376–16391. https://doi.org/10.3934/math.2024793 doi: 10.3934/math.2024793
  • 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(272) PDF downloads(80) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(3)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog