Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

Expand
  • 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 date: 2020-03-17

  Revised date: 2021-09-29

  Online published: 2023-09-07

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

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.

Cite this article

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 . DOI: 10.1007/s40305-021-00375-4

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)
Options
Outlines

/