Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Stancu-Minasian, I.M.: Fractional Programming: Theory, Methods and Applications. Kluwer, Dordrecht (1997)

    Book  MATH  Google Scholar 

  2. Nguyen, T.H.P., Tuy, H.: A unified monotonic approach to generalized linear fractional programming. J. Glob. Optim. 26, 229–259 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  4. Wang, C.F., Liu, S.Y.: A new linearization method for generalized linear multiplicative programming. Comput. Oper. Res. 38, 1008–1013 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Shen, P., Jiao, H.: Linearization method for a class of multiplicative programming with exponent. Appl. Math. Comput. 183(1), 328–336 (2006)

    MathSciNet  MATH  Google Scholar 

  6. Ryoo, H.S., Sahinidis, N.V.: Global optimization of multiplicative programs. J. Glob. Optim. 26, 387–418 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Jiao, H., Liu, S.: Global optimization algorithm for a generalized linear multiplicative programming. J. Appl. Math. Comput. 40(1–2), 551–568 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  11. Shen, P., Li, X.: Branch-reduction-bound algorithm for generalized geometric programming. J. Glob. Optim. 56(3), 1123–1142 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Wang, Y.J., Liang, Z.A.: A deterministic global optimization algorithm for generalized geometric programming. Appl. Math. Comput. 168, 722–737 (2005)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  14. Shen, P.: Linearization method of global optimization for generalized geometric programming. Appl. Math. Comput. 162, 353–370 (2005)

    MathSciNet  MATH  Google Scholar 

  15. Shen, P., Zhang, K.: Global optimization of signomial geometric programming using linear relaxation. Appl. Math. Comput. 150, 99–114 (2004)

    MathSciNet  MATH  Google Scholar 

  16. Shen, P., Li, X., Jiao, H.: Accelerating method of global optimization for signomial geometric programming. J. Comput. Appl. Math. 214, 66–77 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  22. Shen, P., Wang, C.: Global optimization for sum of generalized fractional functions. J. Comput. Appl. Math. 214, 1–12 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  27. Jiao, H.: A branch and bound algorithm for globally solving a class of nonconvex programming problems. Nonlinear Anal-Theor. 70, 1113–1123 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are very grateful to the responsible editors and the anonymous referees for their valuable comments and suggestions, which have greatly improved the earlier version of this paper.

Author information

Authors and Affiliations

  1. Postdoctoral Research Base, Henan Institute of Science and Technology, Xinxiang, 453003, Henan, China

    Hong-Wei Jiao

  2. Postdoctoral Research Station of Control Science and Engineering, Henan University of Science and Technology, Luoyang, 471023, Henan, China

    Hong-Wei Jiao & You-Lin Shang

Authors
  1. Hong-Wei Jiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. You-Lin Shang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hong-Wei Jiao.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this paper.

Additional information

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)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiao, HW., Shang, YL. Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming. J. Oper. Res. Soc. China 11, 569–594 (2023). https://doi.org/10.1007/s40305-021-00375-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-021-00375-4

Keywords

Mathematics Subject Classification

Search

Navigation