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

A spatial branch and bound algorithm for solving the sum of linear ratios optimization problem

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

In this paper, we consider the sum of linear ratios problem (SLR) that is known to be NP-hard and often arises in various practical applications such as data envelopment analysis and financial investment. We first introduce an equivalent problem (EP) of SLR that involves differences of square terms in inequality constraints. Subsequently, the concave parts of the non-convex constraints in problem (EP) are replaced with the piecewise linear functions. Using the resulting second-order cone program (SOCP), we design a spatial branch and bound algorithm, which iteratively refines the piecewise linear approximations by dividing rectangles and solving a series of problems (SOCP) to obtain the solution of the original problem. Also, a region compression technique is proposed to accelerate the convergence of the algorithm. Furthermore, we demonstrate that the bound on the optimality gap is a function of approximation errors at the iteration and estimate that the worst-case number of iterations is in the order of \(\boldsymbol {O(\sqrt {\varepsilon })}\) to attain an ε-optimal solution. Numerical results illustrate that the proposed algorithm scales better than both the existing LP-based algorithms and the off-the-shelf solvers SCIP to solve the problem (SLR). It is worth mentioning that the proposed algorithm takes significantly less time to reach four-digit accuracy than the time required by the known algorithms on small to medium problem instances.

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

Algorithm 1
Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Japan 32(2), 143–158 (1989)

    MathSciNet  MATH  Google Scholar 

  2. Colantoni, C.S., Manes, R.P., Whinston, A.: Programming, profit rates and pricing decisions. Accounting Rev. 44(3), 467–481 (1969)

    Google Scholar 

  3. Konno, H., Watanabe, H.: Bond portfolio optimization problems and their applications to index tracking: a partial optimization approach. J. Oper. Res. Soc. Japan 39(3), 295–306 (1996)

    MathSciNet  MATH  Google Scholar 

  4. Schaible, S.: Fractional programming. Oper. Res. 24(3), 452–461 (2001)

    Article  MATH  Google Scholar 

  5. Sawik, B.: Downside risk approach for multi-objective portfolio optimization. Oper. Res. Proc. 2011, 191–196 (2012)

    MATH  Google Scholar 

  6. Billionnet, A.: Mathematical optimization ideas for biodiversity conservation. Europ. J. Oper. Res. 231, 514–534 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  7. Lim, S., Zhu, J.: Integrated data envelopment analysis: global vs.local optimum. Europ. J. Oper. Res. 229, 276–278 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kao, C.: Network data envelopment analysis: a review. Europ. J. Oper. Res. 239, 1–16 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  9. Jiao, H.W., Liu, S.Y.: A practicable branch and bound algorithm for sum of linear ratios problem. Europ. J. Oper. Res. 243(3), 723–730 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Global Optim. 19, 83–102 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Charnes, A., Cooper, W.W.: Programming with linear fractional functionals. Naval Res. Logistics Quart. 9, 181–186 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  12. Cambini, A., Martein, L., Schaible, S.: On maximizing a sum of ratios. J. Inform. Optim. Sci. 10, 65–79 (1989)

    MathSciNet  MATH  Google Scholar 

  13. Konno, H., Yajima, Y., Matsui, T.: Parametric simplex algorithms for solving a special class of nonconvex minimization problems. J. Global Optim. 1, 65–81 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  14. Benson, H.P.: A simplicial branch and bound duality bounds algorithm for the linear sum of ratios problem. Europ. J. Oper. Res. 182, 597–611 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Zhang, Y.H., Wang, C.F.: A new branch and reduce approach for solving generalized linear fractional programming. Eng. Lett. 25(3), 262–267 (2017)

    Google Scholar 

  16. Shen, P.P., Lu, T.: Regional division and reduction algorithm for minimizing the sum of linear fractional functions. J. Inequalities Appl. 2018, 63 (2018). https://doi.org/10.1186/s13660-018-1651-9

    Article  MathSciNet  MATH  Google Scholar 

  17. Shen, P.P., Li, W.M., Liang, Y.C.: Branch-reduction-bound algorithm for linear sum-of-ratios fractional programs. Pacific J. Optim. 11(1), 79–99 (2015)

    MathSciNet  MATH  Google Scholar 

  18. Liu, S.Y., Ge, L.: An Outcome space algorithm for minimizing a class of linear ratio optimization problems. Comput. Appl. Math. 40, 225 (2021). https://doi.org/10.1007/s40314-021-01614-3

    Article  MathSciNet  MATH  Google Scholar 

  19. Konno, H., Yamashita, H.: Minimizing sums and products of linear fractional functions over a polytope. Naval Res. Logs 46(5), 583–596 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  20. Shen, P.P., Tl, Zhang, Wang, C.F.: Solving a class of generalized fractional programming problems using the feasibility of linear programs. J. Inequal. Appl. 2017, 147 (2017). https://doi.org/10.1186/s13660-017-1420-1

  21. Shen, P.P., Huang, B.D., Wang, L.F.: 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 

  22. Falk, J.E., Palocsay, S.W.: Image space analysis of generalized fractional programs. J. Global Optim. 4, 63–88 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  23. Konno, H., Abe, N.: Minimization of the sum of three linear fractional functions. J. Global Optim. 15, 419–432 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nesterov, Y.E., Nemirovskii, A.S.: An interior-point method for generalized linear-fractional programming. Math. Programming 69, 177–204 (1995)

    Article  MathSciNet  Google Scholar 

  25. Zhang, B., Gao, Y.L.: An output-space based branch-and-bound algorithm for sum-of-linear-ratios problem. Asia-Pacific J. Oper. Res. 22(1), 1–23 (2022)

    MathSciNet  Google Scholar 

  26. Zhang, B., Gao, Y.L., Liu, X., Huang, X.L.: A new deterministic global computing algorithm for solving a kind of linear fractional programming. Optimization. 5(2), 953–957 (2022)

    Google Scholar 

  27. IBM ILOG CPLEX. IBM ILOG CPLEX 12.3 User’s manual for CPLEX 89 (2011)

Download references

Acknowledgements

We would like to thank the editors for their helpful suggestions.

Funding

This research was supported by the National Natural Science Foundation of China (grant number: 12071133;11871196).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Jinshui East Road, Zhengzhou, 450046, Henan, China

    Shen Peiping, Wang Yafei & Wu Dianxiao

Authors
  1. Shen Peiping
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wang Yafei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wu Dianxiao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shen Peiping.

Ethics declarations

Ethics approval and consent to participate

All authors contributed to this work.

Conflict of interest

The authors declare no competing interests.

Additional information

Author contribution

Shen wrote the main content of the paper, Wang and Wu carried out the numerical experiment and provided tables and figures.

Data availability

All data and models generated or used during the study are described in Section 5 of this article.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Shen Peiping, Wang Yafei and Wu Dianxiao contributed to this work.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Peiping, S., Yafei, W. & Dianxiao, W. A spatial branch and bound algorithm for solving the sum of linear ratios optimization problem. Numer Algor 93, 1373–1400 (2023). https://doi.org/10.1007/s11075-022-01471-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-022-01471-z

Keywords

Mathematics Subject Classification (2010)

Search

Navigation