IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v90y2025i1d10.1007_s10589-024-00622-3.html
   My bibliography  Save this article

A New branch-and-cut algorithm for linear sum-of-ratios problem based on SLO method and LO relaxation

Author

Listed:
  • Hezhi Luo

    (Zhejiang Normal University)

  • Youmin Xu

    (Zhejiang Normal University)

  • Huixian Wu

    (Hangzhou Dianzi University)

  • Guoqiang Wang

    (Shanghai University of Engineering Science)

Abstract

We consider a linear sum-of-ratios fractional programming problem that arises from a broad range of applications and is known to be NP-hard. In this paper, we first develop a successive linear optimization (SLO) method for the linear sum-of-ratios problem and show that it converges to a KKT point of the underlying problem. Second, we propose a new branch-and-cut algorithm for globally solving the linear sum-of-ratios fractional program by integrating the SLO method, the linear optimization (LO) relaxation, branch-and-bound framework and branch-and-cut rule. We establish the global convergence of the algorithm and estimate its complexity. Numerical results are reported to illustrate the effectiveness of the proposed algorithm in finding a global optimal solution to large-scale instances of linear sum-of-ratios problem.

Suggested Citation

  • Hezhi Luo & Youmin Xu & Huixian Wu & Guoqiang Wang, 2025. "A New branch-and-cut algorithm for linear sum-of-ratios problem based on SLO method and LO relaxation," Computational Optimization and Applications, Springer, vol. 90(1), pages 257-301, January.
    • Handle: RePEc:spr:coopap:v:90:y:2025:i:1:d:10.1007_s10589-024-00622-3
    DOI: 10.1007/s10589-024-00622-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-024-00622-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-024-00622-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jiao, Hong-Wei & Liu, San-Yang, 2015. "A practicable branch and bound algorithm for sum of linear ratios problem," European Journal of Operational Research, Elsevier, vol. 243(3), pages 723-730.
    2. H. P. Benson, 2010. "Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 1-18, July.
    3. Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2022. "An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 830-855, March.
    4. Kao, Chiang, 2014. "Network data envelopment analysis: A review," European Journal of Operational Research, Elsevier, vol. 239(1), pages 1-16.
    5. H. P. Benson, 2002. "Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem," Journal of Optimization Theory and Applications, Springer, vol. 112(1), pages 1-29, January.
    6. Hiroshi Konno & Hajime Yamashita, 1999. "Minimizing sums and products of linear fractional functions over a polytope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 583-596, August.
    7. Yang, Min & Li, Yongjun & Chen, Ya & Liang, Liang, 2014. "An equilibrium efficiency frontier data envelopment analysis approach for evaluating decision-making units with fixed-sum outputs," European Journal of Operational Research, Elsevier, vol. 239(2), pages 479-489.
    8. Nesterov, Y. & Nemirovskii, A., 1995. "An interior-point method for generalized linear-fractional programming," LIDAM Reprints CORE 1168, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Takahito Kuno & Toshiyuki Masaki, 2013. "A practical but rigorous approach to sum-of-ratios optimization in geometric applications," Computational Optimization and Applications, Springer, vol. 54(1), pages 93-109, January.
    10. Benson, Harold P., 2007. "A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem," European Journal of Operational Research, Elsevier, vol. 182(2), pages 597-611, October.
    11. Chiang Kao, 2014. "Efficiency Decomposition in Network Data Envelopment Analysis," International Series in Operations Research & Management Science, in: Wade D. Cook & Joe Zhu (ed.), Data Envelopment Analysis, edition 127, chapter 0, pages 55-77, Springer.
    12. Faiz A. Al-Khayyal & James E. Falk, 1983. "Jointly Constrained Biconvex Programming," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 273-286, May.
    13. H. P. Benson, 2004. "On the Global Optimization of Sums of Linear Fractional Functions over a Convex Set," Journal of Optimization Theory and Applications, Springer, vol. 121(1), pages 19-39, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2022. "An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 830-855, March.
    2. Jiao, Hongwei & Ma, Junqiao, 2022. "An efficient algorithm and complexity result for solving the sum of general affine ratios problem," Chaos, Solitons & Fractals, Elsevier, vol. 164(C).
    3. Shen, Peiping & Zhu, Zeyi & Chen, Xiao, 2019. "A practicable contraction approach for the sum of the generalized polynomial ratios problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 36-48.
    4. Hongwei Jiao & Binbin Li & Wenqiang Yang, 2024. "A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems," Journal of Global Optimization, Springer, vol. 89(3), pages 597-632, July.
    5. Chen, Ya & Li, Yongjun & Liang, Liang & Salo, Ahti & Wu, Huaqing, 2016. "Frontier projection and efficiency decomposition in two-stage processes with slacks-based measures," European Journal of Operational Research, Elsevier, vol. 250(2), pages 543-554.
    6. Li, Yongjun & Liu, Jin & Ang, Sheng & Yang, Feng, 2021. "Performance evaluation of two-stage network structures with fixed-sum outputs: An application to the 2018winter Olympic Games," Omega, Elsevier, vol. 102(C).
    7. Jiao, Hong-Wei & Liu, San-Yang, 2015. "A practicable branch and bound algorithm for sum of linear ratios problem," European Journal of Operational Research, Elsevier, vol. 243(3), pages 723-730.
    8. Huang, Bingdi & Shen, Peiping, 2024. "An efficient branch and bound reduction algorithm for globally solving linear fractional programming problems," Chaos, Solitons & Fractals, Elsevier, vol. 182(C).
    9. Chen, Ya & Pan, Yongbin & Liu, Haoxiang & Wu, Huaqing & Deng, Guangwei, 2023. "Efficiency analysis of Chinese universities with shared inputs: An aggregated two-stage network DEA approach," Socio-Economic Planning Sciences, Elsevier, vol. 90(C).
    10. Qingyou Yan & Fei Zhao & Xu Wang & Tomas Balezentis, 2021. "The Environmental Efficiency Analysis Based on the Three-Step Method for Two-Stage Data Envelopment Analysis," Energies, MDPI, vol. 14(21), pages 1-14, October.
    11. Xiao, Huijuan & Wang, Daoping & Qi, Yu & Shao, Shuai & Zhou, Ya & Shan, Yuli, 2021. "The governance-production nexus of eco-efficiency in Chinese resource-based cities: A two-stage network DEA approach," Energy Economics, Elsevier, vol. 101(C).
    12. Moraes, Ricardo Kalil & Wanke, Peter Fernandes & Faria, João Ricardo, 2021. "Unveiling the endogeneity between social-welfare and labor efficiency: Two-stage NDEA neural network approach," Socio-Economic Planning Sciences, Elsevier, vol. 77(C).
    13. Koronakos, Gregory & Sotiros, Dimitris & Despotis, Dimitris K. & Kritikos, Manolis N., 2022. "Fair efficiency decomposition in network DEA: A compromise programming approach," Socio-Economic Planning Sciences, Elsevier, vol. 79(C).
    14. Andrey V. Lychev & Svetlana V. Ratner & Vladimir E. Krivonozhko, 2023. "Two-Stage Data Envelopment Analysis Models with Negative System Outputs for the Efficiency Evaluation of Government Financial Policies," Mathematics, MDPI, vol. 11(24), pages 1-21, December.
    15. Ibrahim Alnafrah, 2021. "Efficiency evaluation of BRICS’s national innovation systems based on bias-corrected network data envelopment analysis," Journal of Innovation and Entrepreneurship, Springer, vol. 10(1), pages 1-28, December.
    16. Kao, Chiang, 2022. "A maximum slacks-based measure of efficiency for closed series production systems," Omega, Elsevier, vol. 106(C).
    17. Svetlana V. Ratner & Artem M. Shaposhnikov & Andrey V. Lychev, 2023. "Network DEA and Its Applications (2017–2022): A Systematic Literature Review," Mathematics, MDPI, vol. 11(9), pages 1-24, May.
    18. Vitor Miguel Ribeiro & Celeste Varum & Ana Dias Daniel, 2021. "Introducing microeconomic foundation in data envelopment analysis: effects of the ex ante regulation principle on regional performance," Journal of the Knowledge Economy, Springer;Portland International Center for Management of Engineering and Technology (PICMET), vol. 12(3), pages 1215-1244, September.
    19. Kao, Chiang, 2016. "Efficiency decomposition and aggregation in network data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 255(3), pages 778-786.
    20. Claudio Pinto, 2021. "Performances Management When Modelling Internal Structure of a Production Process," International Journal of Business and Management, Canadian Center of Science and Education, vol. 15(7), pages 133-133, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:90:y:2025:i:1:d:10.1007_s10589-024-00622-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.