• Previous Article
    Analysis of $ {{M}^{({{\lambda }_{1}}, {{\lambda }_{2}})}}/G/1 $ queue with uninterrupted single vacation and server's workload controlled D-policy
  • JIMO Home
  • This Issue
  • Next Article
    Quality investment strategies in a complementary supply chain with an unreliable supplier
doi: 10.3934/jimo.2022135
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Effective algorithm and computational complexity for solving sum of linear ratios problem

1. 

School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang 453003, China

2. 

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

3. 

School of Management, Northwestern Polytechnical University, Xi'an 710072, China

*Corresponding author: Hongwei Jiao

Received  December 2021 Revised  June 2022 Early access August 2022

Fund Project: The first author is supported by the National Natural Science Foundation of China (11871196; 12071133), China Postdoctoral Science Foundation (2017M622340), the Key Scientific and Technological Research Projects in Henan Province (202102210147; 192102210114)

This paper presents an effective algorithm for globally solving the sum of linear ratios problem (SLRP), which has broad applications in government planning, finance and investment, cluster analysis, game theory and so on. In this paper, by using a new linearization technique, the linear relaxation problem of the equivalent problem is constructed. Next, based on the linear relaxation problem and the branch-and-bound framework, an effective branch-and-bound algorithm for globally solving the problem (SLRP) is proposed. By analyzing the computational complexity of the proposed algorithm, the maximum number of iterations of the algorithm is derived. Numerical experiments are reported to verify the effectiveness and feasibility of the proposed algorithm. Finally, two practical application problems from power transportation and production planning are solved to verify the feasibility of the algorithm.

Citation: Hongwei Jiao, Junqiao Ma, Peiping Shen, Yongjian Qiu. Effective algorithm and computational complexity for solving sum of linear ratios problem. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022135
References:
[1]

E. B. Bajalinov, Linear-Fractional Programming: Theory, Methods, Applications and Software, Kluwer Academic Publishers, Dordrecht, 2003.

[2]

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.  doi: 10.1016/j.ejor.2006.08.036.

[3]

H. P. Benson, Branch and bound outer approximation algorithm for sum-of-ratios fractional programs, J. Optim. Theory Appl., 146 (2010), 1-18. doi: 10.1007/s10957-010-9647-8.

[4]

H. P. Benson, Global optimization algorithm for the nonlinear sum of ratios problem, J. Optim. Theory Appl., 112 (2002), 1-29.  doi: 10.1023/A:1013072027218.

[5]

H. P. Benson, Using concave envelopes to globally solve the nonlinear sum of ratios problem, J. Global Optim., 22 (2002), 343-364.  doi: 10.1023/A:1013869015288.

[6]

J. G. Carlsson and J. Shi, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Oper. Res. Lett., 41 (2013), 381-389.  doi: 10.1016/j.orl.2013.04.005.

[7]

J. E. Falk and S. W. Palocsay, Optimizing the sum of linear fractional functions, Recent Advances in Global Optimization (Princeton, NJ, 1991), Princeton Ser. Comput. Sci., Princeton Univ. Press, Princeton, NJ, (1992), 221–258 doi: 10.1515/9781400862528.221.

[8]

R. W. Freund and F. Jarre, Solving the sum-of-ratios problem by an interior-point method, J. Global Optim., 19 (2001), 83-102.  doi: 10.1023/A:1008316327038.

[9]

Y. Gao and S. Jin, A global optimization algorithm for sum of linear ratios problem, J. Appl. Math., (2013), Art. ID 276245, 7 pp. doi: 10.1155/2013/276245.

[10]

B. Huang and P. Shen, Global optimization algorithm for solving sum of linear ratios problems, Pac. J. Optim., 18 (2022), 177-194. 

[11]

J. E. Falk and S. W. Palocsay, Image space analysis of generalized fractional programs, J. Global Optim., 4 (1994), 63-88.  doi: 10.1007/BF01096535.

[12]

H.-W. Jiao and S.-Y. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243 (2015), 723-730.  doi: 10.1016/j.ejor.2015.01.039.

[13]

H. JiaoS. LiuJ. Yin and Y. Zhao, Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 14 (2016), 736-746.  doi: 10.1515/math-2016-0058.

[14]

H. Jiao, Y. Shang and R. Chen, A potential practical algorithm for minimizing the sum of affine fractional functions, Optimization, (2022), 2032051. doi: 10.1080/02331934.2022.2032051.

[15]

H. JiaoY. Shang and W. Wang, Solving generalized polynomial problem by using new affine relaxed technique, Int. J. Comput. Math., 99 (2022), 309-331.  doi: 10.1080/00207160.2021.1909727.

[16]

H.-W. Jiao and Y.-L. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc. China, (2022). doi: 10.1007/s40305-021-00375-4.

[17]

H. Jiao and Y. Shang, Image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem, J. Comput. Math., (2022).

[18]

H. JiaoJ. Ma and Y. Shang, Image space branch-and-bound algorithm for globally solving minimax linear fractional programming problem, Pac. J. Optim., 18 (2022), 195-212. 

[19]

H. JiaoW. WangJ. Yin and Y. Shang, Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems, RAIRO-Oper. Res., 56 (2022), 1533-1552.  doi: 10.1051/ro/2022061.

[20]

T. Kuno, A branch-and-bound algorithm for maximizing the sum of several linear ratios, J. Global Optim., 22 (2002), 155-174.  doi: 10.1023/A:1013807129844.

[21]

H. Konno and M. Inori, Bond portfolio optimization by bilinear fractional programming, J. Oper. Res. Soc. Japan, 32 (1989), 143-158.  doi: 10.15807/jorsj.32.143.

[22]

H. KonnoY. Yajima and T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Global Optim., 1 (1991), 65-81.  doi: 10.1007/BF00120666.

[23]

H. Konno and H. Yamashita, Minimizing sums and products of linear fractional functions over a polytope, Nav. Res. Log., 46 (1999), 583-596.  doi: 10.1002/(SICI)1520-6750(199908)46:5<583::AID-NAV8>3.0.CO;2-5.

[24]

H. Konno and H. Watanabe, Bond portfolio optimization problems and their applications to index tracking: A partial optimization approach, J. Oper. Res. Soc. Japan, 39 (1996), 295-306.  doi: 10.15807/jorsj.39.295.

[25]

Y. E. Nesterov and A. S. Nemirovskii, An interior point method for generalized linear-fractional programming, Math. Program., 69 (1995), 177-204.  doi: 10.1007/BF01585557.

[26]

B. A. Ozkok, An iterative algorithm to solve a linear fractional programming problem, Comput. Ind. Eng., 140 (2020), 106234.  doi: 10.1016/j.cie.2019.106234.

[27]

N. T. H. Phuong and H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Global Optim., 26 (2003), 229-259.  doi: 10.1023/A:1023274721632.

[28]

M. R. Rao, Cluster analysis and mathematical programming, J. Am. Stat. Assoc., 66 (1971), 622-626.  doi: 10.1080/01621459.1971.10482319.

[29]

P. ShenB. Huang and L. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324-342.  doi: 10.1016/j.cam.2018.10.038.

[30]

P.-P. Shen and T. Lu, Regional division and reduction algorithm for minimizing the sum of linear fractional functions, J. Inequal. Appl., 2018 (2018), Paper No. 63, 19 pp. doi: 10.1186/s13660-018-1651-9.

[31]

P.-P. Shen and C.-F. Wang, Global optimization for sum of linear ratios problem with coefficients, Appl. Math. Comput., 176 (2006), 219-229.  doi: 10.1016/j.amc.2005.09.047.

[32]

P. Shen, T. Zhang and C. Wang, Solving a class of generalized fractional programming problems using the feasibility of linear programs, J. Inequal. Appl., 2017 (2017), Paper No. 147, 16 pp. doi: 10.1186/s13660-017-1420-1.

[33]

P. ShenZ. Zhu and X. Chen, A practicable contraction approach for the sum of the generalized polynomial ratios problem, Eur. J. Oper. Res., 278 (2019), 36-48.  doi: 10.1016/j.ejor.2019.03.014.

[34]

Y. Shi, Global Optimization for Sum of Ratios Problems, MA Thesis, Henan Normal University, 2011.

[35]

I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), 439-470.  doi: 10.1080/02331934.2016.1276179.

[36]

D. Zhang and D. Adelman, An approximate dynamic programming approach to network revenue management with customer choice, Transport. Sci., 43 (2009), 381-394.  doi: 10.1287/trsc.1090.0262.

[37]

B. Zhang, Y. Gao, X. Liu and X. Huang, A new deterministic global computing algorithm for solving a kind of linear fractional programming, Optimization, (2022), 2027940. doi: 10.1080/02331934.2022.2027940.

show all references

References:
[1]

E. B. Bajalinov, Linear-Fractional Programming: Theory, Methods, Applications and Software, Kluwer Academic Publishers, Dordrecht, 2003.

[2]

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.  doi: 10.1016/j.ejor.2006.08.036.

[3]

H. P. Benson, Branch and bound outer approximation algorithm for sum-of-ratios fractional programs, J. Optim. Theory Appl., 146 (2010), 1-18. doi: 10.1007/s10957-010-9647-8.

[4]

H. P. Benson, Global optimization algorithm for the nonlinear sum of ratios problem, J. Optim. Theory Appl., 112 (2002), 1-29.  doi: 10.1023/A:1013072027218.

[5]

H. P. Benson, Using concave envelopes to globally solve the nonlinear sum of ratios problem, J. Global Optim., 22 (2002), 343-364.  doi: 10.1023/A:1013869015288.

[6]

J. G. Carlsson and J. Shi, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Oper. Res. Lett., 41 (2013), 381-389.  doi: 10.1016/j.orl.2013.04.005.

[7]

J. E. Falk and S. W. Palocsay, Optimizing the sum of linear fractional functions, Recent Advances in Global Optimization (Princeton, NJ, 1991), Princeton Ser. Comput. Sci., Princeton Univ. Press, Princeton, NJ, (1992), 221–258 doi: 10.1515/9781400862528.221.

[8]

R. W. Freund and F. Jarre, Solving the sum-of-ratios problem by an interior-point method, J. Global Optim., 19 (2001), 83-102.  doi: 10.1023/A:1008316327038.

[9]

Y. Gao and S. Jin, A global optimization algorithm for sum of linear ratios problem, J. Appl. Math., (2013), Art. ID 276245, 7 pp. doi: 10.1155/2013/276245.

[10]

B. Huang and P. Shen, Global optimization algorithm for solving sum of linear ratios problems, Pac. J. Optim., 18 (2022), 177-194. 

[11]

J. E. Falk and S. W. Palocsay, Image space analysis of generalized fractional programs, J. Global Optim., 4 (1994), 63-88.  doi: 10.1007/BF01096535.

[12]

H.-W. Jiao and S.-Y. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243 (2015), 723-730.  doi: 10.1016/j.ejor.2015.01.039.

[13]

H. JiaoS. LiuJ. Yin and Y. Zhao, Outcome space range reduction method for global optimization of sum of affine ratios problem, Open Math., 14 (2016), 736-746.  doi: 10.1515/math-2016-0058.

[14]

H. Jiao, Y. Shang and R. Chen, A potential practical algorithm for minimizing the sum of affine fractional functions, Optimization, (2022), 2032051. doi: 10.1080/02331934.2022.2032051.

[15]

H. JiaoY. Shang and W. Wang, Solving generalized polynomial problem by using new affine relaxed technique, Int. J. Comput. Math., 99 (2022), 309-331.  doi: 10.1080/00207160.2021.1909727.

[16]

H.-W. Jiao and Y.-L. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc. China, (2022). doi: 10.1007/s40305-021-00375-4.

[17]

H. Jiao and Y. Shang, Image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem, J. Comput. Math., (2022).

[18]

H. JiaoJ. Ma and Y. Shang, Image space branch-and-bound algorithm for globally solving minimax linear fractional programming problem, Pac. J. Optim., 18 (2022), 195-212. 

[19]

H. JiaoW. WangJ. Yin and Y. Shang, Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems, RAIRO-Oper. Res., 56 (2022), 1533-1552.  doi: 10.1051/ro/2022061.

[20]

T. Kuno, A branch-and-bound algorithm for maximizing the sum of several linear ratios, J. Global Optim., 22 (2002), 155-174.  doi: 10.1023/A:1013807129844.

[21]

H. Konno and M. Inori, Bond portfolio optimization by bilinear fractional programming, J. Oper. Res. Soc. Japan, 32 (1989), 143-158.  doi: 10.15807/jorsj.32.143.

[22]

H. KonnoY. Yajima and T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Global Optim., 1 (1991), 65-81.  doi: 10.1007/BF00120666.

[23]

H. Konno and H. Yamashita, Minimizing sums and products of linear fractional functions over a polytope, Nav. Res. Log., 46 (1999), 583-596.  doi: 10.1002/(SICI)1520-6750(199908)46:5<583::AID-NAV8>3.0.CO;2-5.

[24]

H. Konno and H. Watanabe, Bond portfolio optimization problems and their applications to index tracking: A partial optimization approach, J. Oper. Res. Soc. Japan, 39 (1996), 295-306.  doi: 10.15807/jorsj.39.295.

[25]

Y. E. Nesterov and A. S. Nemirovskii, An interior point method for generalized linear-fractional programming, Math. Program., 69 (1995), 177-204.  doi: 10.1007/BF01585557.

[26]

B. A. Ozkok, An iterative algorithm to solve a linear fractional programming problem, Comput. Ind. Eng., 140 (2020), 106234.  doi: 10.1016/j.cie.2019.106234.

[27]

N. T. H. Phuong and H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Global Optim., 26 (2003), 229-259.  doi: 10.1023/A:1023274721632.

[28]

M. R. Rao, Cluster analysis and mathematical programming, J. Am. Stat. Assoc., 66 (1971), 622-626.  doi: 10.1080/01621459.1971.10482319.

[29]

P. ShenB. Huang and L. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324-342.  doi: 10.1016/j.cam.2018.10.038.

[30]

P.-P. Shen and T. Lu, Regional division and reduction algorithm for minimizing the sum of linear fractional functions, J. Inequal. Appl., 2018 (2018), Paper No. 63, 19 pp. doi: 10.1186/s13660-018-1651-9.

[31]

P.-P. Shen and C.-F. Wang, Global optimization for sum of linear ratios problem with coefficients, Appl. Math. Comput., 176 (2006), 219-229.  doi: 10.1016/j.amc.2005.09.047.

[32]

P. Shen, T. Zhang and C. Wang, Solving a class of generalized fractional programming problems using the feasibility of linear programs, J. Inequal. Appl., 2017 (2017), Paper No. 147, 16 pp. doi: 10.1186/s13660-017-1420-1.

[33]

P. ShenZ. Zhu and X. Chen, A practicable contraction approach for the sum of the generalized polynomial ratios problem, Eur. J. Oper. Res., 278 (2019), 36-48.  doi: 10.1016/j.ejor.2019.03.014.

[34]

Y. Shi, Global Optimization for Sum of Ratios Problems, MA Thesis, Henan Normal University, 2011.

[35]

I. M. Stancu-Minasian, A eighth bibliography of fractional programming, Optimization, 66 (2017), 439-470.  doi: 10.1080/02331934.2016.1276179.

[36]

D. Zhang and D. Adelman, An approximate dynamic programming approach to network revenue management with customer choice, Transport. Sci., 43 (2009), 381-394.  doi: 10.1287/trsc.1090.0262.

[37]

B. Zhang, Y. Gao, X. Liu and X. Huang, A new deterministic global computing algorithm for solving a kind of linear fractional programming, Optimization, (2022), 2027940. doi: 10.1080/02331934.2022.2027940.

Figure 1.  Numerical comparisons between our algorithm and that of Jiao and Liu [12] on the average number of iteration (left) and the average CPU time (right) for Example 13 with the fixed $ p = 2 $ and $ m = 100 $
Table 1.  Numerical comparison between some existing algorithms and our algorithm on test Examples 1-12
No. Algorithms Opt. val. Optimal solution Iter. Time $ \epsilon $
1 Our algorithm -4.84151 (0.1000, 2.37500) 0 0.006 $ 10^{-2} $
Benson [2] -4.84151 (0.1000, 2.3750) 4 0.190 $ 10^{-2} $
Jiao & Liu [12] -4.84151 (0.1000, 2.3750) 200 4.257 $ 10^{-2} $
2 Our algorithm -2.47143 (1.0000, 0.0000, 0.0000) 2 0.056 $ 10^{-2} $
Shen et al. [29] -2.47143 (1.0000, 0.0000, 0.0000) 2 0.015 $ 10^{-2} $
Jiao & Liu [12] -2.47124 (1.0001, 0.0000, 0.0001) 54 1.135 $ 10^{-2} $
3 Our algorithm -1.90000 (0.0000, 3.3333, 0.0000) 0 0.007 $ 10^{-6} $
[0.5mm] Shen & Wang [31] -1.90000 (0.0000, 3.3333, 0.0000) 8 0.926 $ 10^{-6} $
4 Our algorithm 1.62320 (0.0000, 0.2875) 91 1.895 $ 10^{-2} $
Jiao & Liu [12] 1.62319 (0.0000, 0.2861) 93 2.485 $ 10^{-2} $
5 Our algorithm 2.86190 (5.0000, 0.0000, 0.0000) 5 0.062 $ 10^{-3} $
Jiao & Liu [12] 2.86241 (4.8302, 0.0000, 0.0666) 4008 128.0 $ 10^{-3} $
Shen & Lu [30] 2.86191 (5.0000, 0.0000, 0.0000) 16 0.125 $ 10^{-3} $
Gao & Jin [9] 2.86190 (5.0000, 0.0000, 0.0000) 12 28.29 $ 10^{-3} $
6 Our algorithm -4.09070 (1.1111, 0.0000, 0.0000) 0 0.006 $ 10^{-2} $
Jiao & Liu [12] -4.09062 (1.1106, 0.0000, 0.0015) 619 16.62 $ 10^{-2} $
Shen & Lu [30] -4.08741 (1.0715, 0.0000, 0.0000) 17 3.251 $ 10^{-2} $
7 Our algorithm 3.71092 (0.0000, 1.6667, 0.0000) 0 0.007 $ 10^{-4} $
Jiao & Liu [12] 3.71093 (0.0000, 1.6667, 0.0000) 2747 94.64 $ 10^{-4} $
Gao & Jin [9] 3.7087 (0.0000, 1.6667, 0.0000) 5 4.190 $ 10^{-4} $
8 Our algorithm -3.00292 (0.0000, 3.3333, 0.0000) 19 0.414 $ 10^{-6} $
Jiao & Liu [12] -3.00292 (0.0000, 3.3333, 0.0000) 1072 31.746 $ 10^{-2} $
9 Our algorithm 4.91259 (1.5000, 1.5000) 35 0.388 $ 10^{-3} $
Shen & Lu [30] 4.91259 (1.5000, 1.5000) 56 1.087 $ 10^{-3} $
10 Our algorithm -4.09070 (1.1111, 0.0000, 0.0000) 0 0.007 $ 10^{-6} $
Jiao et al. [13] -4.09070 (1.1111, 0.0000, 0.0000) 2 0.008 $ 10^{-6} $
Jiao & Liu [12] -4.09065 (1.1109, 0.0000, 0.0005) 977 32.41 $ 10^{-6} $
11 Our algorithm 3.29167 (3.0000, 4.0000) 0 0.007 $ 10^{-6} $
Shen & Wang [31] 3.29167 (3.0000, 4.0000) 9 0.489 $ 10^{-6} $
12 Our algorithm 4.42857 (5.0000, 0.0000, 0.0000) 0 0.006 $ 10^{-4} $
Jiao & Liu [12] 4.42794 (4.9930, 0.0000, 0.0000) 128 4.213 $ 10^{-4} $
Shi [34] 4.42857 (5.0000, 0.0000, 0.0000) 58 2.968 $ 10^{-4} $
No. Algorithms Opt. val. Optimal solution Iter. Time $ \epsilon $
1 Our algorithm -4.84151 (0.1000, 2.37500) 0 0.006 $ 10^{-2} $
Benson [2] -4.84151 (0.1000, 2.3750) 4 0.190 $ 10^{-2} $
Jiao & Liu [12] -4.84151 (0.1000, 2.3750) 200 4.257 $ 10^{-2} $
2 Our algorithm -2.47143 (1.0000, 0.0000, 0.0000) 2 0.056 $ 10^{-2} $
Shen et al. [29] -2.47143 (1.0000, 0.0000, 0.0000) 2 0.015 $ 10^{-2} $
Jiao & Liu [12] -2.47124 (1.0001, 0.0000, 0.0001) 54 1.135 $ 10^{-2} $
3 Our algorithm -1.90000 (0.0000, 3.3333, 0.0000) 0 0.007 $ 10^{-6} $
[0.5mm] Shen & Wang [31] -1.90000 (0.0000, 3.3333, 0.0000) 8 0.926 $ 10^{-6} $
4 Our algorithm 1.62320 (0.0000, 0.2875) 91 1.895 $ 10^{-2} $
Jiao & Liu [12] 1.62319 (0.0000, 0.2861) 93 2.485 $ 10^{-2} $
5 Our algorithm 2.86190 (5.0000, 0.0000, 0.0000) 5 0.062 $ 10^{-3} $
Jiao & Liu [12] 2.86241 (4.8302, 0.0000, 0.0666) 4008 128.0 $ 10^{-3} $
Shen & Lu [30] 2.86191 (5.0000, 0.0000, 0.0000) 16 0.125 $ 10^{-3} $
Gao & Jin [9] 2.86190 (5.0000, 0.0000, 0.0000) 12 28.29 $ 10^{-3} $
6 Our algorithm -4.09070 (1.1111, 0.0000, 0.0000) 0 0.006 $ 10^{-2} $
Jiao & Liu [12] -4.09062 (1.1106, 0.0000, 0.0015) 619 16.62 $ 10^{-2} $
Shen & Lu [30] -4.08741 (1.0715, 0.0000, 0.0000) 17 3.251 $ 10^{-2} $
7 Our algorithm 3.71092 (0.0000, 1.6667, 0.0000) 0 0.007 $ 10^{-4} $
Jiao & Liu [12] 3.71093 (0.0000, 1.6667, 0.0000) 2747 94.64 $ 10^{-4} $
Gao & Jin [9] 3.7087 (0.0000, 1.6667, 0.0000) 5 4.190 $ 10^{-4} $
8 Our algorithm -3.00292 (0.0000, 3.3333, 0.0000) 19 0.414 $ 10^{-6} $
Jiao & Liu [12] -3.00292 (0.0000, 3.3333, 0.0000) 1072 31.746 $ 10^{-2} $
9 Our algorithm 4.91259 (1.5000, 1.5000) 35 0.388 $ 10^{-3} $
Shen & Lu [30] 4.91259 (1.5000, 1.5000) 56 1.087 $ 10^{-3} $
10 Our algorithm -4.09070 (1.1111, 0.0000, 0.0000) 0 0.007 $ 10^{-6} $
Jiao et al. [13] -4.09070 (1.1111, 0.0000, 0.0000) 2 0.008 $ 10^{-6} $
Jiao & Liu [12] -4.09065 (1.1109, 0.0000, 0.0005) 977 32.41 $ 10^{-6} $
11 Our algorithm 3.29167 (3.0000, 4.0000) 0 0.007 $ 10^{-6} $
Shen & Wang [31] 3.29167 (3.0000, 4.0000) 9 0.489 $ 10^{-6} $
12 Our algorithm 4.42857 (5.0000, 0.0000, 0.0000) 0 0.006 $ 10^{-4} $
Jiao & Liu [12] 4.42794 (4.9930, 0.0000, 0.0000) 128 4.213 $ 10^{-4} $
Shi [34] 4.42857 (5.0000, 0.0000, 0.0000) 58 2.968 $ 10^{-4} $
Table 2.  Numerical comparison among our algorithm, the Solver Baron, and the algorithm presented in Jiao & Liu [12] on test Example 13
$ (p,m,n) $ Our algorithm Algorithm of Jiao & Liu [12] Solver Baron
Avg.Iter Avg.Time Avg.Iter Avg.Time
(2,100, 1000) 3.2 9.564 875.7 181.876 1.4 61.801
(2,100, 2000) 3.3 40.168 796.6 565.931 1.2 157.389
(2,100, 3000) 3.7 95.127 957.5 1429.668 1.6 221.738
(2,100, 4000) 3.6 166.269 806.2 2103.738 1.0 464.433
(2,100, 5000) 3.9 272.254 787.5 3192.184 1.2 686.963
(3,100, 1000) 5.6 31.742 $ \ast $ $ \ast $ 2.6 68.283
(4,100, 1000) 8.0 71.107 $ \ast $ $ \ast $ 3.8 105.082
(5,100, 1000) 12.5 165.760 $ \ast $ $ \ast $ 4.4 172.502
$ (p,m,n) $ Our algorithm Algorithm of Jiao & Liu [12] Solver Baron
Avg.Iter Avg.Time Avg.Iter Avg.Time
(2,100, 1000) 3.2 9.564 875.7 181.876 1.4 61.801
(2,100, 2000) 3.3 40.168 796.6 565.931 1.2 157.389
(2,100, 3000) 3.7 95.127 957.5 1429.668 1.6 221.738
(2,100, 4000) 3.6 166.269 806.2 2103.738 1.0 464.433
(2,100, 5000) 3.9 272.254 787.5 3192.184 1.2 686.963
(3,100, 1000) 5.6 31.742 $ \ast $ $ \ast $ 2.6 68.283
(4,100, 1000) 8.0 71.107 $ \ast $ $ \ast $ 3.8 105.082
(5,100, 1000) 12.5 165.760 $ \ast $ $ \ast $ 4.4 172.502
Table 3.  Numerical results of our algorithm for the production planning problem
$ (m, n) $ \text {Time(s)} \text {Iter} $ (m, n) $ \text {Time(s)} \text {Iter}
(10, 10) 0.00819 1.0 (750,750) 0.09992 1.0
(50, 50) 0.01039 1.0 (1000, 1000) 0.12572 1.0
(100,100) 0.00849 1.0 (1500, 1500) 0.28695 1.0
(250,250) 0.01436 1.0 (2000, 2000) 0.48897 1.0
(500,500) 0.03895 1.0 (1000, 3000) 0.61870 1.0
$ (m, n) $ \text {Time(s)} \text {Iter} $ (m, n) $ \text {Time(s)} \text {Iter}
(10, 10) 0.00819 1.0 (750,750) 0.09992 1.0
(50, 50) 0.01039 1.0 (1000, 1000) 0.12572 1.0
(100,100) 0.00849 1.0 (1500, 1500) 0.28695 1.0
(250,250) 0.01436 1.0 (2000, 2000) 0.48897 1.0
(500,500) 0.03895 1.0 (1000, 3000) 0.61870 1.0
[1]

Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647

[2]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[3]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[4]

Ahmet Sahiner, Nurullah Yilmaz, Gulden Kapusuz. A novel modeling and smoothing technique in global optimization. Journal of Industrial and Management Optimization, 2019, 15 (1) : 113-130. doi: 10.3934/jimo.2018035

[5]

Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059

[6]

Xuefeng Zhang, Hui Yan. Image enhancement algorithm using adaptive fractional differential mask technique. Mathematical Foundations of Computing, 2019, 2 (4) : 347-359. doi: 10.3934/mfc.2019022

[7]

Miklós Horváth, Márton Kiss. A bound for ratios of eigenvalues of Schrodinger operators on the real line. Conference Publications, 2005, 2005 (Special) : 403-409. doi: 10.3934/proc.2005.2005.403

[8]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

[9]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775

[10]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial and Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[11]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032

[12]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[13]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[14]

Rui Qian, Rong Hu, Ya-Ping Fang. Local smooth representation of solution sets in parametric linear fractional programming problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 45-52. doi: 10.3934/naco.2019004

[15]

Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343

[16]

René Carmona, Kenza Hamidouche, Mathieu Laurière, Zongjun Tan. Linear-quadratic zero-sum mean-field type games: Optimality conditions and policy optimization. Journal of Dynamics and Games, 2021, 8 (4) : 403-443. doi: 10.3934/jdg.2021023

[17]

Enkhbat Rentsen, J. Zhou, K. L. Teo. A global optimization approach to fractional optimal control. Journal of Industrial and Management Optimization, 2016, 12 (1) : 73-82. doi: 10.3934/jimo.2016.12.73

[18]

Anna Cima, Armengol Gasull, Francesc Mañosas. Global linearization of periodic difference equations. Discrete and Continuous Dynamical Systems, 2012, 32 (5) : 1575-1595. doi: 10.3934/dcds.2012.32.1575

[19]

Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[20]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (96)
  • HTML views (62)
  • Cited by (0)

[Back to Top]