IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i12d10.1057_s41274-017-0185-8.html
   My bibliography  Save this article

Cutting plane approach for the maximum flow interdiction problem

Author

Listed:
  • Joe Naoum-Sawaya

    (Western University)

  • Bissan Ghaddar

    (University of Waterloo)

Abstract

The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.

Suggested Citation

  • Joe Naoum-Sawaya & Bissan Ghaddar, 2017. "Cutting plane approach for the maximum flow interdiction problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(12), pages 1553-1569, December.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:12:d:10.1057_s41274-017-0185-8
    DOI: 10.1057/s41274-017-0185-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-017-0185-8
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-017-0185-8?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. Willard I. Zangwill, 1969. "A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System--A Network Approach," Management Science, INFORMS, vol. 15(9), pages 506-527, May.
    2. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    3. Ken Ambs & Sebastian Cwilich & Mei Deng & David J. Houck & David F. Lynch & Dicky Yan, 2000. "Optimizing Restoration Capacity in the AT&T Network," Interfaces, INFORMS, vol. 30(1), pages 26-44, February.
    4. Joe Naoum-Sawaya & Christoph Buchheim, 2016. "Robust Critical Node Selection by Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 162-174, February.
    5. Myung, Young-Soo & Kim, Hyun-joon, 2004. "A cutting plane algorithm for computing k-edge survivability of a network," European Journal of Operational Research, Elsevier, vol. 156(3), pages 579-589, August.
    6. (Noel) Bryson, Kweku-Muata & Millar, Harvey & Joseph, Anito & Mobolurin, Ayodele, 2002. "Using formal MS/OR modeling to support disaster recovery planning," European Journal of Operational Research, Elsevier, vol. 141(3), pages 679-688, September.
    7. Equi, Luisa & Gallo, Giorgio & Marziale, Silvia & Weintraub, Andres, 1997. "A combined transportation and scheduling problem," European Journal of Operational Research, Elsevier, vol. 97(1), pages 94-104, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.

    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. Altay, Nezih & Green III, Walter G., 2006. "OR/MS research in disaster operations management," European Journal of Operational Research, Elsevier, vol. 175(1), pages 475-493, November.
    2. Sahebjamnia, Navid & Torabi, S. Ali & Mansouri, S. Afshin, 2018. "Building organizational resilience in the face of multiple disruptions," International Journal of Production Economics, Elsevier, vol. 197(C), pages 63-83.
    3. Torabi, S.A. & Mansouri, S.A., 2015. "Integrated business continuity and disaster recovery planning: Towards organizational resilienceAuthor-Name: Sahebjamnia, N," European Journal of Operational Research, Elsevier, vol. 242(1), pages 261-273.
    4. Timothy Matisziw & Alan Murray & Tony Grubesic, 2010. "Strategic Network Restoration," Networks and Spatial Economics, Springer, vol. 10(3), pages 345-361, September.
    5. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    6. Brech, Claus-Henning & Ernst, Andreas & Kolisch, Rainer, 2019. "Scheduling medical residents’ training at university hospitals," European Journal of Operational Research, Elsevier, vol. 274(1), pages 253-266.
    7. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    8. Preece, Gary & Shaw, Duncan & Hayashi, Haruo, 2013. "Using the Viable System Model (VSM) to structure information processing complexity in disaster response," European Journal of Operational Research, Elsevier, vol. 224(1), pages 209-218.
    9. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    10. García Cáceres, Rafael Guillermo & Aráoz Durand, Julián Arturo & Gómez, Fernando Palacios, 2009. "Integral analysis method - IAM," European Journal of Operational Research, Elsevier, vol. 192(3), pages 891-903, February.
    11. Osman, Hany & Demirli, Kudret, 2010. "A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection," International Journal of Production Economics, Elsevier, vol. 124(1), pages 97-105, March.
    12. Chia-Lee Yang & Benjamin J. C. Yuan & Chi-Yo Huang, 2015. "Key Determinant Derivations for Information Technology Disaster Recovery Site Selection by the Multi-Criterion Decision Making Method," Sustainability, MDPI, vol. 7(5), pages 1-40, May.
    13. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    14. Xiao, Yiyong & Kaku, Ikou & Zhao, Qiuhong & Zhang, Renqian, 2011. "A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 214(2), pages 223-231, October.
    15. Lahlum, Suzanne M. & Dooley, Frank J., 1996. "The Optimal Number and Size of Fertilizer Plants Under Hazardous Materials Regulations," MPC Reports 231704, North Dakota State University, Upper Great Plains Transportation Institute.
    16. Kajjoune, Oussama & Aouam, Tarik & Zouadi, Tarik & Ranjan, Ravi Prakash, 2023. "Dynamic lot-sizing in a two-stage supply chain with liquidity constraints and financing options," International Journal of Production Economics, Elsevier, vol. 258(C).
    17. Karakose, Gokhan & McGarvey, Ronald G., 2018. "Capacitated path-aggregation constraint model for arc disruption in networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 225-238.
    18. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    19. Kerkkamp, R.B.O. & van den Heuvel, W. & Wagelmans, A.P.M., 2019. "Two-echelon lot-sizing with asymmetric information and continuous type space," Omega, Elsevier, vol. 87(C), pages 158-176.
    20. Zio, E., 2018. "The future of risk assessment," Reliability Engineering and System Safety, Elsevier, vol. 177(C), pages 176-190.

    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:pal:jorsoc:v:68:y:2017:i:12:d:10.1057_s41274-017-0185-8. 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.palgrave-journals.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.