IDEAS home Printed from https://ideas.repec.org/a/kap/compec/v63y2024i6d10.1007_s10614-023-10407-1.html
   My bibliography  Save this article

A Hybrid Parallel Processing Strategy for Large-Scale DEA Computation

Author

Listed:
  • Shengqing Chang

    (Hefei University of Technology)

  • Jingjing Ding

    (Hefei University of Technology
    Intelligent Interconnection System Anhui Provincial Laboratory
    (Hefei University of Technology), Ministry of Education)

  • Chenpeng Feng

    (Hefei University of Technology
    Intelligent Interconnection System Anhui Provincial Laboratory
    (Hefei University of Technology), Ministry of Education)

  • Ruifeng Wang

    (SPD Bank)

Abstract

Using data envelopment analysis (DEA) with large-scale data poses a big challenge to applications due to its computing-intensive nature. So far, various strategies have been proposed in academia to accelerate the DEA computation, including DEA algorithms such as hierarchical decomposition (HD), DEA enhancements such as restricted basis entry (RBE) and LP accelerators such as hot starts. However, few studies have integrated these strategies and combined them with a parallel processing framework to solve large-scale DEA problems. In this paper, a hybrid parallel DEA algorithm (named PRHH algorithm) is proposed, including the RBE algorithm, hot starts, and HD algorithm based on Message Passing Interface (MPI). Furthermore, the attribute of the PRHH algorithm is analyzed, and formalized as a computing time function, to shed light on its time complexity. Finally, the performance of the algorithm is investigated in various simulation scenarios with datasets of different characteristics and compared with existing methods. The results show that the proposed algorithm reduces computing time in general, and boosts performance dramatically in scenarios with low density in particular.

Suggested Citation

  • Shengqing Chang & Jingjing Ding & Chenpeng Feng & Ruifeng Wang, 2024. "A Hybrid Parallel Processing Strategy for Large-Scale DEA Computation," Computational Economics, Springer;Society for Computational Economics, vol. 63(6), pages 2325-2349, June.
    • Handle: RePEc:kap:compec:v:63:y:2024:i:6:d:10.1007_s10614-023-10407-1
    DOI: 10.1007/s10614-023-10407-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10614-023-10407-1
    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/s10614-023-10407-1?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. Chen, Yao & Iqbal Ali, Agha, 2002. "Output-input ratio analysis and DEA frontier," European Journal of Operational Research, Elsevier, vol. 142(3), pages 476-479, November.
    2. Charnes, A. & Cooper, W. W. & Rhodes, E., 1978. "Measuring the efficiency of decision making units," European Journal of Operational Research, Elsevier, vol. 2(6), pages 429-444, November.
    3. Richard Barr & Matthew Durchholz, 1997. "Parallel and hierarchical decomposition approaches for solving large-scale Data Envelopment Analysis models," Annals of Operations Research, Springer, vol. 73(0), pages 339-372, October.
    4. Wen-Chih Chen & Sheng-Yung Lai, 2017. "Determining radial efficiency with a large data set by solving small-size linear programs," Annals of Operations Research, Springer, vol. 250(1), pages 147-166, March.
    5. Dula, J. H. & Helgason, R. V., 1996. "A new procedure for identifying the frame of the convex hull of a finite collection of points in multidimensional space," European Journal of Operational Research, Elsevier, vol. 92(2), pages 352-367, July.
    6. Tao Jie, 2020. "Parallel processing of the Build Hull algorithm to address the large-scale DEA problem," Annals of Operations Research, Springer, vol. 295(1), pages 453-481, December.
    7. Yande Gong & Joe Zhu & Ya Chen & Wade D. Cook, 2018. "DEA as a tool for auditing: application to Chinese manufacturing industry with parallel network structures," Annals of Operations Research, Springer, vol. 263(1), pages 247-269, April.
    8. J. H. Dulá & R. V. Helgason & N. Venugopal, 1998. "An Algorithm for Identifying the Frame of a Pointed Finite Conical Hull," INFORMS Journal on Computing, INFORMS, vol. 10(3), pages 323-330, August.
    9. Shaojian Qu & Lei Xu & Sachin Kumar Mangla & Felix T. S. Chan & Jianli Zhu & Sobhan Arisian, 2022. "Matchmaking in reward-based crowdfunding platforms: a hybrid machine learning approach," International Journal of Production Research, Taylor & Francis Journals, vol. 60(24), pages 7551-7571, December.
    10. R. D. Banker & A. Charnes & W. W. Cooper, 1984. "Some Models for Estimating Technical and Scale Inefficiencies in Data Envelopment Analysis," Management Science, INFORMS, vol. 30(9), pages 1078-1092, September.
    11. Ali, Agha Iqbal, 1993. "Streamlined computation for data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 64(1), pages 61-67, January.
    12. Shaojian Qu & Can Feng & Shan Jiang & Jinpeng Wei & Yuting Xu, 2022. "Data-Driven Robust DEA Models for Measuring Operational Efficiency of Endowment Insurance System of Different Provinces in China," Sustainability, MDPI, vol. 14(16), pages 1-21, August.
    13. Shaojian Qu & Yuting Xu & Ying Ji & Can Feng & Jinpeng Wei & Shan Jiang, 2022. "Data-Driven Robust Data Envelopment Analysis for Evaluating the Carbon Emissions Efficiency of Provinces in China," Sustainability, MDPI, vol. 14(20), pages 1-26, October.
    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. Khezrimotlagh, Dariush & Zhu, Joe & Cook, Wade D. & Toloo, Mehdi, 2019. "Data envelopment analysis and big data," European Journal of Operational Research, Elsevier, vol. 274(3), pages 1047-1054.
    2. Chu, Junfei & Rui, Yuting & Khezrimotlagh, Dariush & Zhu, Joe, 2024. "A general computational framework and a hybrid algorithm for large-scale data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 316(2), pages 639-650.
    3. Wen-Chih Chen & Sheng-Yung Lai, 2017. "Determining radial efficiency with a large data set by solving small-size linear programs," Annals of Operations Research, Springer, vol. 250(1), pages 147-166, March.
    4. J. H. Dulá, 2011. "An Algorithm for Data Envelopment Analysis," INFORMS Journal on Computing, INFORMS, vol. 23(2), pages 284-296, May.
    5. Tao Jie, 2020. "Parallel processing of the Build Hull algorithm to address the large-scale DEA problem," Annals of Operations Research, Springer, vol. 295(1), pages 453-481, December.
    6. López, Francisco J., 2011. "Generalizing cross redundancy in data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 214(3), pages 716-721, November.
    7. Khezrimotlagh, Dariush & Cook, Wade D. & Zhu, Joe, 2020. "A nonparametric framework to detect outliers in estimating production frontiers," European Journal of Operational Research, Elsevier, vol. 286(1), pages 375-388.
    8. Valentin Zelenyuk, 2019. "Data Envelopment Analysis and Business Analytics: The Big Data Challenges and Some Solutions," CEPA Working Papers Series WP072019, School of Economics, University of Queensland, Australia.
    9. Zelenyuk, Valentin, 2020. "Aggregation of inputs and outputs prior to Data Envelopment Analysis under big data," European Journal of Operational Research, Elsevier, vol. 282(1), pages 172-187.
    10. Peter Fernandes Wanke & Rebecca de Mattos, 2014. "Capacity Issues and Efficiency Drivers in Brazilian Bulk Terminals," Brazilian Business Review, Fucape Business School, vol. 11(5), pages 72-98, October.
    11. Ali, Agha Iqbal & Lerme, Catherine S. & Seiford, Lawrence M., 1995. "Components of efficiency evaluation in data envelopment analysis," European Journal of Operational Research, Elsevier, vol. 80(3), pages 462-473, February.
    12. Ming-Fu Hsu & Ying-Shao Hsin & Fu-Jiing Shiue, 2022. "Business analytics for corporate risk management and performance improvement," Annals of Operations Research, Springer, vol. 315(2), pages 629-669, August.
    13. Premachandra, I. M., 2001. "A note on DEA vs principal component analysis: An improvement to Joe Zhu's approach," European Journal of Operational Research, Elsevier, vol. 132(3), pages 553-560, August.
    14. Liu, W.B. & Zhang, D.Q. & Meng, W. & Li, X.X. & Xu, F., 2011. "A study of DEA models without explicit inputs," Omega, Elsevier, vol. 39(5), pages 472-480, October.
    15. Xie, Qiwei & Xu, Qifan & Zhu, Da & Rao, Kaifeng & Dai, Qianzhi, 2020. "Fair allocation of wastewater discharge permits based on satisfaction criteria using data envelopment analysis," Utilities Policy, Elsevier, vol. 66(C).
    16. M Soleimani-damaneh, 2009. "A fast algorithm for determining some characteristics in DEA," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(11), pages 1528-1534, November.
    17. Saeid Mehrabian & Gholam R. Jahanshahloo & Mohammad R. Alirezaee & Gholam R. Amin, 2000. "An Assurance Interval for the Non-Archimedean Epsilon in DEA Models," Operations Research, INFORMS, vol. 48(2), pages 344-347, April.
    18. Yi-Shian Lee & Lee-Ing Tong, 2012. "Predicting High or Low Transfer Efficiency of Photovoltaic Systems Using a Novel Hybrid Methodology Combining Rough Set Theory, Data Envelopment Analysis and Genetic Programming," Energies, MDPI, vol. 5(3), pages 1-16, February.
    19. Alexander P. Afanasiev & Vladimir E. Krivonozhko & Andrey V. Lychev & Oleg V. Sukhoroslov, 2020. "Multidimensional frontier visualization based on optimization methods using parallel computations," Journal of Global Optimization, Springer, vol. 76(3), pages 563-574, March.
    20. Qiwei Xie & Yuanyuan Li & Lizheng Wang & Chao Liu, 2018. "Improving discrimination in data envelopment analysis without losing information based on Renyi’s entropy," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(4), pages 1053-1068, December.

    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:kap:compec:v:63:y:2024:i:6:d:10.1007_s10614-023-10407-1. 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.