IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v12y2020i2p581-d308086.html
   My bibliography  Save this article

Dynamic Gaming Case of the R-Interdiction Median Problem with Fortification and an MILP-Based Solution Approach

Author

Listed:
  • Yiyong Xiao

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

  • Pei Yang

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

  • Siyue Zhang

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

  • Shenghan Zhou

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

  • Wenbing Chang

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

  • Yue Zhang

    (School of Reliability and System Engineering, Beihang University, Beijing 100191, China)

Abstract

This paper studies the cyclic dynamic gaming case of the r -interdiction median problem with fortification (CDGC-RIMF), which is important for strengthening a facility’s reliability and invulnerability under various possible attacks. We formulated the CDGC-RIMF as a bi-objective mixed-integer linear programming (MILP) model with two opposing goals to minimize/maximize the loss from both the designer (leader) and attacker (follower) sides. The first goal was to identify the most cost-effective plan to build and fortify the facility considering minimum loss, whereas the attacker followed the designer to seek the most destructive way of attacking to cause maximum loss. We found that the two sides could not reach a static equilibrium with a single pair of confrontational plans in an ordinary case, but were able to reach a dynamically cyclic equilibrium when the plan involved multiple pairs. The proposed bi-objective model aimed to discover the optimal cyclic plans for both sides to reach a dynamic equilibrium. To solve this problem, we first started from the designer’s side with a design and fortification plan, and then the attacker was able to generate their worst attack plan based on that design. After that, the designer changed their plan again based on the attacker’s plan in order to minimize loss, and the attacker correspondingly modified their plan to achieve maximum loss. This game looped until, finally, a cyclic equilibrium was reached. This equilibrium was deemed to be optimal for both sides because there was always more loss for either side if they left the equilibrium first. This game falls into the subgame of a perfect Nash equilibrium—a kind of complete game. The proposed bi-objective model was directly solved by the CPLEX solver to achieve optimal solutions for small-sized problems and near-optimal feasible solutions for larger-sized problems. Furthermore, for large-scale problems, we developed a heuristic algorithm that implemented dynamic iterative partial optimization alongside MILP (DIPO-MILP), which showed better performance compared with the CPLEX solver when solving large-scale problems.

Suggested Citation

  • Yiyong Xiao & Pei Yang & Siyue Zhang & Shenghan Zhou & Wenbing Chang & Yue Zhang, 2020. "Dynamic Gaming Case of the R-Interdiction Median Problem with Fortification and an MILP-Based Solution Approach," Sustainability, MDPI, vol. 12(2), pages 1-17, January.
    • Handle: RePEc:gam:jsusta:v:12:y:2020:i:2:p:581-:d:308086
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/12/2/581/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/12/2/581/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Scaparra, Maria P. & Church, Richard L., 2008. "An exact solution approach for the interdiction median problem with fortification," European Journal of Operational Research, Elsevier, vol. 189(1), pages 76-92, August.
    2. 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.
    3. Marcos Costa Roboredo & Luiz Aizemberg & Artur Alves Pessoa, 2019. "An exact approach for the r-interdiction covering problem with fortification," 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. 27(1), pages 111-131, March.
    4. Medal, Hugh R. & Pohl, Edward A. & Rossetti, Manuel D., 2014. "A multi-objective integrated facility location-hardening model: Analyzing the pre- and post-disruption tradeoff," European Journal of Operational Research, Elsevier, vol. 237(1), pages 257-270.
    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. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Harun, Sarah, 2020. "A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption," European Journal of Operational Research, Elsevier, vol. 285(2), pages 670-694.
    2. Bhatt, Sneha Dhyani & Sinha, Ankur & Jayaswal, Sachin, 2024. "The capacitated r-hub interdiction problem with congestion: Models and solution approaches," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    3. Sarhadi, Hassan & Tulett, David M. & Verma, Manish, 2017. "An analytical approach to the protection planning of a rail intermodal terminal network," European Journal of Operational Research, Elsevier, vol. 257(2), pages 511-525.
    4. Losada, Chaya & Scaparra, M. Paola & O’Hanley, Jesse R., 2012. "Optimizing system resilience: A facility protection model with recovery time," European Journal of Operational Research, Elsevier, vol. 217(3), pages 519-530.
    5. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    6. Ghaffarinasab, Nader & Atayi, Reza, 2018. "An implicit enumeration algorithm for the hub interdiction median problem with fortification," European Journal of Operational Research, Elsevier, vol. 267(1), pages 23-39.
    7. 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.
    8. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2016. "Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods. (Revised)," IIMA Working Papers WP2016-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    9. Tanınmış, Kübra & Aras, Necati & Altınel, İ. Kuban, 2022. "Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks," European Journal of Operational Research, Elsevier, vol. 297(1), pages 40-52.
    10. Sachuer Bao & Chi Zhang & Min Ouyang & Lixin Miao, 2019. "An integrated tri-level model for enhancing the resilience of facilities against intentional attacks," Annals of Operations Research, Springer, vol. 283(1), pages 87-117, December.
    11. Nicolas Fröhlich & Stefan Ruzika, 2022. "Interdicting facilities in tree networks," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 95-118, April.
    12. Kübra Tanınmış & Markus Sinnl, 2022. "A Branch-and-Cut Algorithm for Submodular Interdiction Games," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2634-2657, September.
    13. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2021. "The impact of congestion on protection decisions in supply networks under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    14. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2017. "Responsive contingency planning of capacitated supply networks under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 102(C), pages 13-37.
    15. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2018. "Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches," European Journal of Operational Research, Elsevier, vol. 270(1), pages 230-245.
    16. Girish Ch. Dey & Mamata Jenamani, 2019. "Optimizing fortification plan of capacitated facilities with maximum distance limits," OPSEARCH, Springer;Operational Research Society of India, vol. 56(1), pages 151-173, March.
    17. Li, Qingwei & Savachkin, Alex, 2013. "A heuristic approach to the design of fortified distribution networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 138-148.
    18. 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.
    19. Michael Stiglmayr & José Figueira & Kathrin Klamroth, 2014. "On the multicriteria allocation problem," Annals of Operations Research, Springer, vol. 222(1), pages 535-549, November.
    20. Kaiyue Zheng & Laura A. Albert, 2019. "A Robust Approach for Mitigating Risks in Cyber Supply Chains," Risk Analysis, John Wiley & Sons, vol. 39(9), pages 2076-2092, 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:gam:jsusta:v:12:y:2020:i:2:p:581-:d:308086. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.