IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v161y2014i2d10.1007_s10957-013-0378-5.html
   My bibliography  Save this article

Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations

Author

Listed:
  • Bita Tadayon

    (University of Florida)

  • J. Cole Smith

    (University of Florida)

Abstract

In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity’s path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.

Suggested Citation

  • Bita Tadayon & J. Cole Smith, 2014. "Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations," Journal of Optimization Theory and Applications, Springer, vol. 161(2), pages 506-532, May.
    • Handle: RePEc:spr:joptap:v:161:y:2014:i:2:d:10.1007_s10957-013-0378-5
    DOI: 10.1007/s10957-013-0378-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-013-0378-5
    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/s10957-013-0378-5?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. Jeff L. Kennington, 1978. "A Survey of Linear Cost Multicommodity Network Flows," Operations Research, INFORMS, vol. 26(2), pages 209-236, April.
    2. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    3. Joseph C. Hudson & Kailash C. Kapur, 1985. "Reliability Bounds for Multistate Systems with Multistate Components," Operations Research, INFORMS, vol. 33(1), pages 153-160, February.
    4. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    5. Bezalel Gavish & Kemal Altinkemer, 1990. "Backbone Network Design Tools with Economic Tradeoffs," INFORMS Journal on Computing, INFORMS, vol. 2(3), pages 236-252, August.
    6. April K. Andreas & J. Cole Smith, 2008. "Mathematical Programming Algorithms for Two-Path Routing Problems with Reliability Considerations," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 553-564, November.
    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. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.
    2. Jinil Han & Kyungsik Lee & Chungmok Lee & Sungsoo Park, 2013. "Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 585-596, August.
    3. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    4. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    5. Seohee Kim & Chungmok Lee, 2021. "A branch and price approach for the robust bandwidth packing problem with queuing delays," Annals of Operations Research, Springer, vol. 307(1), pages 251-275, December.
    6. Masri, H. & Krichen, S. & Guitouni, A., 2015. "A multi-start variable neighborhood search for solving the single path multicommodity flow problem," Applied Mathematics and Computation, Elsevier, vol. 251(C), pages 132-142.
    7. Hela Masri & Saoussen Krichen, 2018. "Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem," Annals of Operations Research, Springer, vol. 267(1), pages 353-377, August.
    8. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    9. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    10. Ali Amiri & Hasan Pirkul, 1997. "Routing in packet‐switched communication networks with different criticality classes of communicating node pairs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(5), pages 485-505, August.
    11. Linos F. Frantzeskakis & Hanan Luss, 1999. "The network redesign problem for access telecommunications networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 487-506, August.
    12. Gamvros, Ioannis & Raghavan, S., 2012. "Multi-period traffic routing in satellite networks," European Journal of Operational Research, Elsevier, vol. 219(3), pages 738-750.
    13. Pillac, Victor & Van Hentenryck, Pascal & Even, Caroline, 2016. "A conflict-based path-generation heuristic for evacuation planning," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 136-150.
    14. Yu Zhou & Leishan Zhou & Yun Wang & Xiaomeng Li & Zhuo Yang, 2017. "A practical model for the train-set utilization: The case of Beijing-Tianjin passenger dedicated line in China," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-24, May.
    15. Amy Cohn & Sarah Root & Alex Wang & Douglas Mohr, 2007. "Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers," Transportation Science, INFORMS, vol. 41(2), pages 238-252, May.
    16. F. Sibel Salman & R. Ravi & John N. Hooker, 2008. "Solving the Capacitated Local Access Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 243-254, May.
    17. Trivella, Alessio & Corman, Francesco & Koza, David F. & Pisinger, David, 2021. "The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 150(C).
    18. Peeters, M. & Kroon, L.G., 2003. "Circulation of Railway Rolling Stock: A Branch-and-Price Approach," ERIM Report Series Research in Management ERS-2003-055-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    19. Esteban Inga & Roberto Hincapié & Sandra Céspedes, 2019. "Capacitated Multicommodity Flow Problem for Heterogeneous Smart Electricity Metering Communications Using Column Generation," Energies, MDPI, vol. 13(1), pages 1-21, December.
    20. Desai, Jitamitra & Sen, Suvrajeet, 2010. "A global optimization algorithm for reliable network design," European Journal of Operational Research, Elsevier, vol. 200(1), pages 1-8, January.

    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:joptap:v:161:y:2014:i:2:d:10.1007_s10957-013-0378-5. 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.