IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v44y2022i1d10.1007_s10878-021-00823-0.html
   My bibliography  Save this article

A novel approach to subgraph selection with multiple weights on arcs

Author

Listed:
  • Mohammad Ali Raayatpanah

    (Kharazmi University)

  • Salman Khodayifar

    (Institute for Advanced Studies in Basic Sciences (IASBS))

  • Thomas Weise

    (Hefei University)

  • Panos Pardalos

    (University of Florida
    LATNA, Higher School of Economics)

Abstract

In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs for routing the flow. The problem is tractable when a single weight is given on each arc. However, in many real-world applications, several weights are needed to describe the features of arcs, including transit cost, arrival time, delay, profit, security, reliability, deterioration, and safety. In this case, finding an optimal solution becomes difficult. We propose a heuristic algorithm for this purpose. First, we compute the relative efficiency of the arcs by using data envelopment analysis techniques. We then determine a subgraph with efficient arcs using a linear programming model, where the objective function is based on the relative efficiency of the arcs. The flow obtained satisfies the arc capacity constraints and the integrality property. Our proposed algorithm has polynomial runtime and is evaluated in rigorous experiments.

Suggested Citation

  • Mohammad Ali Raayatpanah & Salman Khodayifar & Thomas Weise & Panos Pardalos, 2022. "A novel approach to subgraph selection with multiple weights on arcs," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 242-268, August.
    • Handle: RePEc:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00823-0
    DOI: 10.1007/s10878-021-00823-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-021-00823-0
    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/s10878-021-00823-0?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. 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.
    2. Richard D. McBride & John W. Mamer, 1997. "Solving Multicommodity Flow Problems with a Primal Embedded Network Simplex Algorithm," INFORMS Journal on Computing, INFORMS, vol. 9(2), pages 154-163, May.
    3. Darwin Klingman, 1977. "Finding Equivalent Network Formulations for Constrained Network Problems," Management Science, INFORMS, vol. 23(7), pages 737-744, March.
    4. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    5. Joe Zhu, 2014. "Data Envelopment Analysis," International Series in Operations Research & Management Science, in: Quantitative Models for Performance Evaluation and Benchmarking, edition 3, chapter 1, pages 1-9, Springer.
    6. F. Glover & Darwin Klingman & G. Terry Ross, 1974. "Finding equivalent transportation formulations for constrained transportation problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(2), pages 247-254, June.
    7. Longkun Guo, 2016. "Efficient approximation algorithms for computing k disjoint constrained shortest paths," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 144-158, July.
    8. Michael Holzhauser & Sven O. Krumke & Clemens Thielen, 2016. "Budget-constrained minimum cost flows," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1720-1745, May.
    9. McBride, Richard D., 1985. "Solving embedded generalized network problems," European Journal of Operational Research, Elsevier, vol. 21(1), pages 82-92, July.
    10. Cook, Wade D. & Tone, Kaoru & Zhu, Joe, 2014. "Data envelopment analysis: Prior to choosing a model," Omega, Elsevier, vol. 44(C), pages 1-4.
    11. Hamacher, Horst W. & Pedersen, Christian Roed & Ruzika, Stefan, 2007. "Multiple objective minimum cost flow problems: A review," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1404-1422, February.
    12. Yongwen Hu & Xiao Zhao & Jing Liu & Binyuan Liang & Chao Ma, 2020. "An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions," Mathematical Problems in Engineering, Hindawi, vol. 2020, pages 1-5, February.
    13. Yang, Guo-liang & Yang, Jian-bo & Liu, Wen-bin & Li, Xiao-xuan, 2013. "Cross-efficiency aggregation in DEA models using the evidential-reasoning approach," European Journal of Operational Research, Elsevier, vol. 231(2), pages 393-404.
    14. Alireza Amirteimoori, 2011. "An extended transportation problem: a DEA-based approach," 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. 19(4), pages 513-521, December.
    15. Prahalad Venkateshan & Kamlesh Mathur & Ronald H. Ballou, 2008. "An efficient generalized network-simplex-based algorithm for manufacturing network flows," Journal of Combinatorial Optimization, Springer, vol. 15(4), pages 315-341, May.
    16. John W. Mamer & Richard D. McBride, 2000. "A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem," Management Science, INFORMS, vol. 46(5), pages 693-709, May.
    17. Haiyan Lu & Enyu Yao & Liqun Qi, 2006. "Some further results on minimum distribution cost flow problems," Journal of Combinatorial Optimization, Springer, vol. 11(4), pages 351-371, June.
    18. William W. Cooper & Lawrence M. Seiford & Kaoru Tone, 2006. "Introduction to Data Envelopment Analysis and Its Uses," Springer Books, Springer, number 978-0-387-29122-2, December.
    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. ÇalIskan, Cenk, 2011. "A specialized network simplex algorithm for the constrained maximum flow problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 137-147, April.
    2. Sarmento, Joaquim Miranda & Renneboog, Luc & Verga-Matos, Pedro, 2017. "Measuring highway efficiency : A DEA approach and the Malquist index," Other publications TiSEM 23264815-321e-45a3-83ee-9, Tilburg University, School of Economics and Management.
    3. Avkiran, Necmi Kemal, 2015. "An illustration of dynamic network DEA in commercial banking including robustness tests," Omega, Elsevier, vol. 55(C), pages 141-150.
    4. Michael Kourtis & Panayiotis Curtis & Michael Hanias & Eleftherios Kourtis, 2021. "A Strategic Financial Management Evaluation of Private Hospitals’ Effectiveness and Efficiency for Sustainable Financing: A Research Study," European Research Studies Journal, European Research Studies Journal, vol. 0(1), pages 1025-1054.
    5. Congcong Yang & Alfred Taudes & Guozhi Dong, 2017. "Efficiency analysis of European Freight Villages: three peers for benchmarking," 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. 25(1), pages 91-122, March.
    6. Ming-Chung Chang & Chiang-Ping Chen & Chien-Cheng Lin & Yu-Ming Xu, 2022. "The Overall and Disaggregate China’s Bank Efficiency from Sustainable Business Perspectives," Sustainability, MDPI, vol. 14(7), pages 1-16, April.
    7. 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).
    8. Silvia Saravia-Matus & T. S. Amjath-Babu & Sreejith Aravindakshan & Stefan Sieber & Jimmy A. Saravia & Sergio Gomez y Paloma, 2021. "Can Enhancing Efficiency Promote the Economic Viability of Smallholder Farmers? A Case of Sierra Leone," Sustainability, MDPI, vol. 13(8), pages 1-17, April.
    9. Yash Daultani & Ashish Dwivedi & Saurabh Pratap, 2021. "Benchmarking higher education institutes using data envelopment analysis: capturing perceptions of prospective engineering students," OPSEARCH, Springer;Operational Research Society of India, vol. 58(4), pages 773-789, December.
    10. Ying Li & Yung-Ho Chiu & Tai-Yu Lin & Tzu-Han Chang, 2020. "Pre-Evaluating the Technical Efficiency Gains from Potential Mergers and Acquisitions in the IC Design Industry," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 19(02), pages 525-559, April.
    11. Amar Oukil & Slim Zekri, 2021. "Investigating farming efficiency through a two stage analytical approach: Application to the agricultural sector in Northern Oman," Papers 2104.10943, arXiv.org.
    12. Olawale Ogunrinde & Ekundayo Shittu, 2023. "Benchmarking performance of photovoltaic power plants in multiple periods," Environment Systems and Decisions, Springer, vol. 43(3), pages 489-503, September.
    13. Park, Jaehun & Lee, Dongha & Zhu, Joe, 2014. "An integrated approach for ship block manufacturing process performance evaluation: Case from a Korean shipbuilding company," International Journal of Production Economics, Elsevier, vol. 156(C), pages 214-222.
    14. Trinks, Arjan & Mulder, Machiel & Scholtens, Bert, 2020. "An Efficiency Perspective on Carbon Emissions and Financial Performance," Ecological Economics, Elsevier, vol. 175(C).
    15. Geng, ZhiQiang & Dong, JunGen & Han, YongMing & Zhu, QunXiong, 2017. "Energy and environment efficiency analysis based on an improved environment DEA cross-model: Case study of complex chemical processes," Applied Energy, Elsevier, vol. 205(C), pages 465-476.
    16. Toloo, Mehdi & Hančlová, Jana, 2020. "Multi-valued measures in DEA in the presence of undesirable outputs," Omega, Elsevier, vol. 94(C).
    17. Babak Daneshvar Rouyendegh & Asil Oztekin & Joseph Ekong & Ali Dag, 2019. "Measuring the efficiency of hospitals: a fully-ranking DEA–FAHP approach," Annals of Operations Research, Springer, vol. 278(1), pages 361-378, July.
    18. Andreas Eder & Bernhard Mahlberg, 2018. "Size, Subsidies and Technical Efficiency in Renewable Energy Production: The Case of Austrian Biogas Plants," The Energy Journal, , vol. 39(1), pages 185-210, January.
    19. Maha Kalai, 2019. "Nonparametric Measures of Capacity Utilization of the Tunisian Manufacturing Industry: Short- and Long-Run Dual Approach," Journal of the Knowledge Economy, Springer;Portland International Center for Management of Engineering and Technology (PICMET), vol. 10(1), pages 318-334, March.
    20. Cook, Wade D. & Ruiz, José L. & Sirvent, Inmaculada & Zhu, Joe, 2017. "Within-group common benchmarking using DEA," European Journal of Operational Research, Elsevier, vol. 256(3), pages 901-910.

    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:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00823-0. 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.