Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

doi:10.1007/s40305-021-00375-4

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (3): 569-594.doi: 10.1007/s40305-021-00375-4

Previous Articles Next Articles

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

Hong-Wei Jiao^1,2, You-Lin Shang²

1. Postdoctoral Research Base, Henan Institute of Science and Technology, Xinxiang, 453003, Henan, China;
2. Postdoctoral Research Station of Control Science and Engineering, Henan University of Science and Technology, Luoyang, 471023, Henan, China

Received:2020-03-17 Revised:2021-09-29 Online:2023-09-30 Published:2023-09-07
Contact: Hong-Wei Jiao, You-Lin Shang E-mail:jiaohongwei@126.com;mathshang@sina.com
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11871196, 12071133 and 12071112), the China Postdoctoral Science Foundation (No. 2017M622340), the Key Scientific and Technological Research Projects of Henan Province (Nos. 202102210147 and 192102210114), the Science and Technology Climbing Program of Henan Institute of Science and Technology (No. 2018JY01).

Abstract

Abstract: This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem. For establishing this algorithm, we firstly construct a two-level linear relaxation method, and by utilizing the method, we can convert the initial generalized linear fractional programming problem and its subproblems into a series of linear programming relaxation problems. Based on the branch-and-bound framework and linear programming relaxation problems, a branch-and-bound algorithm is presented for globally solving the generalized linear fractional programming problem, and the computational complexity of the algorithm is given. Finally, numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.

Key words: Generalized linear fractional programming, Global optimization, Two-level linear relaxation method, Branch-and-bound

CLC Number:

90C26
90C32

Hong-Wei Jiao, You-Lin Shang. Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming[J]. Journal of the Operations Research Society of China, 2023, 11(3): 569-594.

TrendMD

References

[1] Stancu-Minasian, I.M.: Fractional Programming: Theory, Methods and Applications. Kluwer, Dordrecht (1997)
[2] Nguyen, T.H.P., Tuy, H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259(2003)
[3] Gao, Y.L., Xu, C.X., Yan, Y.L.: An outcome-space finite algorithm for solving linear multiplicative programming. Appl. Math. Comput. 179(2), 494–505(2006)
[4] Wang, C.F., Liu, S.Y.: A new linearization method for generalized linear multiplicative programming. Comput. Oper. Res. 38, 1008–1013(2011)
[5] Shen, P., Jiao, H.: Linearization method for a class of multiplicative programming with exponent. Appl. Math. Comput. 183(1), 328–336(2006)
[6] Ryoo, H.S., Sahinidis, N.V.: Global optimization of multiplicative programs. J. Glob. Optim. 26, 387–418(2003)
[7] Jiao, H., Liu, S.: Global optimization algorithm for a generalized linear multiplicative programming. J. Appl. Math. Comput. 40(1–2), 551–568(2012)
[8] Jiao, H., Liu, S., Yin, J., Zhao, Y.: Outcome space range reduction method for global optimization of sum of linear ratios problems. Open Math. 14, 736–746(2016)
[9] Jiao, H., Liu, S.: Range division and compression algorithm for quadratically constrained sum of quadratic ratios. Comput. Appl. Math. 36(1), 225–247(2017)
[10] Jiao, H., Liu, S.: A practicable branch and bound algorithm for sum of linear ratios problem. Eur. J. Oper. Res. 243(3), 723–730(2015)
[11] Shen, P., Li, X.: Branch-reduction-bound algorithm for generalized geometric programming. J. Glob. Optim. 56(3), 1123–1142(2013)
[12] Wang, Y.J., Liang, Z.A.: A deterministic global optimization algorithm for generalized geometric programming. Appl. Math. Comput. 168, 722–737(2005)
[13] Gao, Y., Xu, C., Wang, Y., Zhang, L.: A new two-level linear relaxed bound method for geometric programming problems. Appl. Math. Comput. 164(1), 117–131(2005)
[14] Shen, P.: Linearization method of global optimization for generalized geometric programming. Appl. Math. Comput. 162, 353–370(2005)
[15] Shen, P., Zhang, K.: Global optimization of signomial geometric programming using linear relaxation. Appl. Math. Comput. 150, 99–114(2004)
[16] Shen, P., Li, X., Jiao, H.: Accelerating method of global optimization for signomial geometric programming. J. Comput. Appl. Math. 214, 66–77(2008)
[17] Jiao, H., Guo, Y., Shen, P.: Global optimization of generalized linear fractional programming with nonlinear constraints. Appl. Math. Comput. 183(2), 717–728(2006)
[18] Liu, X., Gao, Y., Zhang, B., Tian, F.: A new global optimization algorithm for a class of linear fractional programming. Mathematics 7, 867(2019)
[19] Zhang, B., Gao, Y., Liu, X., Huang, X.: Output-space branch-and-bound reduction algorithm for a class of linear multiplicative programs. Mathematics 8, 315(2020)
[20] Shen, P., Huang, B., Wang, L.: Range division and linearization algorithm for a class of linear ratios optimization problems. J. Comput. Appl. Math. 350, 324–342(2019)
[21] Shen, P., Zhu, Z., Chen, X.: A practicable contraction approach for the sum of the generalized polynomial ratios problem. Eur. J. Oper. Res. 278(1), 36–48(2019)
[22] Shen, P., Wang, C.: Global optimization for sum of generalized fractional functions. J. Comput. Appl. Math. 214, 1–12(2008)
[23] Jiao, H., Liu, S.: An efficient algorithm for quadratic sum-of-ratios fractional programs problem. Numer. Func. Anal. Opt. 38(11), 1426–1445(2017)
[24] Gao Y., Jin S.: A global optimization algorithm for sum of linear ratios problem, J. Appl. Math. (2013), Article ID 276245, 7 pages
[25] Wang, C., Shen, P.: A global optimization algorithm for linear fractional programming. Appl. Math. Comput. 204, 281–287(2008)
[26] Pei, Y., Zhu, D.: Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region. J. Appl. Math. Comput. 41(1–2), 153–169(2013)
[27] Jiao, H.: A branch and bound algorithm for globally solving a class of nonconvex programming problems. Nonlinear Anal-Theor. 70, 1113–1123(2009)
[28] Jiao, H., Liu, S., Zhao, Y.: Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints. Appl. Math. Model. 39(23–24), 7568–7582(2015)

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	Chen Wang, Dong-Hua Wu. A K-Means Clustering-Based Multiple Importance Sampling Algorithm for Integral Global Optimization [J]. Journal of the Operations Research Society of China, 2023, 11(1): 157-176.
[2]	Qian Yan, Xin-Min Yang, Zhi-You Wu. On Convexification for a Class of Global Optimization Problems [J]. Journal of the Operations Research Society of China, 2022, 10(3): 427-446.
[3]	Zhong-Yu Wang, Yong-Jian Yang. Novel Global Optimization Algorithm with a Space-Filling Curve and Integral Function [J]. Journal of the Operations Research Society of China, 2021, 9(3): 619-640.
[4]	Zhe Zhou, Fu-Sheng Bai. A Stochastic Adaptive Radial Basis Function Algorithm for Costly Black-Box Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(4): 587-610.
[5]	Hong-Bin Yu, Wei-Jia Zeng, Dong-Hua Wu. A Stochastic Level-Value Estimation Method for Global Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(3): 429-444.
[6]	Zhi-You Wu · Fu-Sheng Bai · Jing Tian. Optimization Methods for Box-Constrained Nonlinear Programming Problems Based on Linear Transformation and Lagrange Interpolating Polynomials [J]. Journal of the Operations Research Society of China, 2017, 5(2): 193-.
[7]	Yong-Jian Yang · Meng-Li He · Yue-Lin Gao. Discrete Global Optimization Problems with a Modified Discrete Filled Function [J]. Journal of the Operations Research Society of China, 2015, 3(3): 297-.
[8]	Zhao Sun. A Refined Error Analysis for Fixed-Degree Polynomial Optimization over the Simplex [J]. Journal of the Operations Research Society of China, 2014, 2(3): 379-394.