IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i2p1272-1290.html
   My bibliography  Save this article

Efficient Solution Methods for a General r -Interdiction Median Problem with Fortification

Author

Listed:
  • Kaike Zhang

    (Department of Industrial and Systems Engineering, University of Tennessee, Knoxville, Tennessee 37996)

  • Xueping Li

    (Department of Industrial and Systems Engineering, University of Tennessee, Knoxville, Tennessee 37996)

  • Mingzhou Jin

    (Department of Industrial and Systems Engineering, University of Tennessee, Knoxville, Tennessee 37996)

Abstract

This study generalizes the r -interdiction median (RIM) problem with fortification to simultaneously consider two types of risks: probabilistic exogenous disruptions and endogenous disruptions caused by intentional attacks. We develop a bilevel programming model that includes a lower-level interdiction problem and a higher-level fortification problem to hedge against such risks. We then prove that the interdiction problem is supermodular and subsequently adopt the cuts associated with supermodularity to develop an efficient cutting-plane algorithm to achieve exact solutions. For the fortification problem, we adopt the logic-based Benders decomposition (LBBD) framework to take advantage of the two-level structure and the property that a facility should not be fortified if it is not attacked at the lower level. Numerical experiments show that the cutting-plane algorithm is more efficient than benchmark methods in the literature, especially when the problem size grows. Specifically, with regard to the solution quality, LBBD outperforms the greedy algorithm in the literature with an up-to 13.2% improvement in the total cost, and it is as good as or better than the tree-search implicit enumeration method. Summary of Contribution: This paper studies an r -interdiction median problem with fortification (RIMF) in a supply chain network that simultaneously considers two types of disruption risks: random disruptions that occur probabilistically and disruptions caused by intentional attacks. The problem is to determine the allocation of limited facility fortification resources to an existing network. It is modeled as a bilevel programming model combining a defender’s problem and an attacker’s problem, which generalizes the r -interdiction median problem with probabilistic fortification. This paper is suitable for IJOC in mainly two aspects: (1) The lower-level attacker’s interdiction problem is a challenging high-degree nonlinear model. In the literature, only a total enumeration method has been applied to solve a special case of this problem. By exploring the special structural property of the problem, namely, the supermodularity of the transportation cost function, we developed an exact cutting-plane method to solve the problem to its optimality. Extensive numerical studies were conducted. Hence, this paper fits in the intersection of operations research and computing. (2) We developed an efficient logic-based Benders decomposition algorithm to solve the higher-level defender’s fortification problem. Overall, this study generalizes several important problems in the literature, such as RIM, RIMF, and RIMF with probabilistic fortification (RIMF- p ).

Suggested Citation

  • Kaike Zhang & Xueping Li & Mingzhou Jin, 2022. "Efficient Solution Methods for a General r -Interdiction Median Problem with Fortification," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1272-1290, March.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:2:p:1272-1290
    DOI: 10.1287/ijoc.2021.1111
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1111
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1111?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
    ---><---

    References listed on IDEAS

    as
    1. Tingting Cui & Yanfeng Ouyang & Zuo-Jun Max Shen, 2010. "Reliable Facility Location Design Under the Risk of Disruptions," Operations Research, INFORMS, vol. 58(4-part-1), pages 998-1011, August.
    2. Michael Lim & Mark S. Daskin & Achal Bassamboo & Sunil Chopra, 2010. "A facility reliability problem: Formulation, properties, and algorithm," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(1), pages 58-70, February.
    3. Deniz Aksen & Nuray Piyade & Necati Aras, 2010. "The budget constrained r-interdiction median problem with capacity expansion," 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. 18(3), pages 269-291, September.
    4. Robert Aboolian & Tingting Cui & Zuo-Jun Max Shen, 2013. "An Efficient Approach for Solving Reliable Facility Location Models," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 720-729, November.
    5. Gustavo Angulo & Shabbir Ahmed & Santanu S. Dey, 2016. "Improving the Integer L-Shaped Method," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 483-499, August.
    6. Cui, Tingting & Ouyang, Yanfeng & Shen, Zuo-Jun Max J, 2010. "Reliable Facility Location Design under the Risk of Disruptions," University of California Transportation Center, Working Papers qt5sh2c7pw, University of California Transportation Center.
    7. Zuo-Jun Max Shen & Roger Lezhou Zhan & Jiawei Zhang, 2011. "The Reliable Facility Location Problem: Formulations, Heuristics, and Approximation Algorithms," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 470-482, August.
    8. Liberatore, Federico & Scaparra, Maria P. & Daskin, Mark S., 2012. "Hedging against disruptions with ripple effects in location analysis," Omega, Elsevier, vol. 40(1), pages 21-30, January.
    9. Lawrence V. Snyder & Zümbül Atan & Peng Peng & Ying Rong & Amanda J. Schmitt & Burcu Sinsoysal, 2016. "OR/MS models for supply chain disruptions: a review," IISE Transactions, Taylor & Francis Journals, vol. 48(2), pages 89-109, February.
    10. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    11. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    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. Nader Azad & Elkafi Hassini, 2019. "A Benders Decomposition Method for Designing Reliable Supply Chain Networks Accounting for Multimitigation Strategies and Demand Losses," Transportation Science, INFORMS, vol. 53(5), pages 1287-1312, September.
    2. Azad, Nader & Hassini, Elkafi, 2019. "Recovery strategies from major supply disruptions in single and multiple sourcing networks," European Journal of Operational Research, Elsevier, vol. 275(2), pages 481-501.
    3. Aldrighetti, Riccardo & Battini, Daria & Ivanov, Dmitry & Zennaro, Ilenia, 2021. "Costs of resilience and disruptions in supply chain network design models: A review and future research directions," International Journal of Production Economics, Elsevier, vol. 235(C).
    4. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2021. "Robust facility location under demand uncertainty and facility disruptions," Omega, Elsevier, vol. 103(C).
    5. Mengshi Lu & Lun Ran & Zuo-Jun Max Shen, 2015. "Reliable Facility Location Design Under Uncertain Correlated Disruptions," Manufacturing & Service Operations Management, INFORMS, vol. 17(4), pages 445-455, October.
    6. Luohao Tang & Cheng Zhu & Zaili Lin & Jianmai Shi & Weiming Zhang, 2016. "Reliable Facility Location Problem with Facility Protection," PLOS ONE, Public Library of Science, vol. 11(9), pages 1-24, September.
    7. Yongzhen Li & Xueping Li & Jia Shu & Miao Song & Kaike Zhang, 2022. "A General Model and Efficient Algorithms for Reliable Facility Location Problem Under Uncertain Disruptions," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 407-426, January.
    8. Wang, Zhaodong & Xie, Siyang & Ouyang, Yanfeng, 2022. "Planning reliable service facility location against disruption risks and last-mile congestion in a continuous space," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 123-140.
    9. Albareda-Sambola, Maria & Hinojosa, Yolanda & Puerto, Justo, 2015. "The reliable p-median problem with at-facility service," European Journal of Operational Research, Elsevier, vol. 245(3), pages 656-666.
    10. Zhang, Yanzi & Diabat, Ali & Zhang, Zhi-Hai, 2021. "Reliable closed-loop supply chain design problem under facility-type-dependent probabilistic disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 180-209.
    11. Jabbarzadeh, Armin & Fahimnia, Behnam & Sheu, Jiuh-Biing & Moghadam, Hani Shahmoradi, 2016. "Designing a supply chain resilient to major disruptions and supply/demand interruptions," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 121-149.
    12. José A. Santiváñez & Héctor J. Carlo, 2018. "Reliable capacitated facility location problem with service levels," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 315-341, December.
    13. Cheng, Chun & Qi, Mingyao & Zhang, Ying & Rousseau, Louis-Martin, 2018. "A two-stage robust approach for the reliable logistics network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 185-202.
    14. O’Hanley, Jesse R. & Scaparra, M. Paola & García, Sergio, 2013. "Probability chains: A general linearization technique for modeling reliability in facility location and related problems," European Journal of Operational Research, Elsevier, vol. 230(1), pages 63-75.
    15. Dimitrov, Nedialko B. & Solow, Daniel & Szmerekovsky, Joseph & Guo, Jia, 2017. "Emergency relocation of items using single trips: Special cases of the Multiple Knapsack Assignment Problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 938-942.
    16. Espejo, Inmaculada & Marín, Alfredo & Rodríguez-Chía, Antonio M., 2015. "Capacitated p-center problem with failure foresight," European Journal of Operational Research, Elsevier, vol. 247(1), pages 229-244.
    17. Nader Azad & Georgios Saharidis & Hamid Davoudpour & Hooman Malekly & Seyed Yektamaram, 2013. "Strategies for protecting supply chain networks against facility and transportation disruptions: an improved Benders decomposition approach," Annals of Operations Research, Springer, vol. 210(1), pages 125-163, November.
    18. Fahimnia, Behnam & Jabbarzadeh, Armin & Sarkis, Joseph, 2018. "Greening versus resilience: A supply chain design perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 119(C), pages 129-148.
    19. Robert Aboolian & Tingting Cui & Zuo-Jun Max Shen, 2013. "An Efficient Approach for Solving Reliable Facility Location Models," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 720-729, November.
    20. Asefeh Hasani Goodarzi & Seyed Hessameddin Zegordi & Gülgün Alpan & Isa Nakhai Kamalabadi & Ali Husseinzadeh Kashan, 2021. "Reliable cross-docking location problem under the risk of disruptions," Operational Research, Springer, vol. 21(3), pages 1569-1612, September.

    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:inm:orijoc:v:34:y:2022:i:2:p:1272-1290. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.