Defensive Future Studies

Defensive Future Studies

Optimal Decision-Making Dealing with Enemy Sabotages Using the Maximum Flow Interdiction Problem in Multi-Period Dynamic Networks in Fuzzy Conditions

Document Type : Original Article

Authors
Hamid Bigdeli 1
Salim Bavandi 2
1 Assistant Prof, Institute for the Study of War, AJA Command and Staff University, Tehran, Iran
2 Researcher, Institute for the study of war, AJA Command and Staff University
10.22034/dfsr.2022.547832.1570
Abstract
For a long time, one of the most important problems in wars has been the enemy's operations to destroy facilities and communication networks. The destruction of bridges and roads, air, missile, or artillery attacks, and the countless cyber-attacks in recent years prove that one of the main goals of the enemy in wars is to weaken through the destruction of facilities and equipment. In contrast, the defense forces seek to make the most of their resources and facilities to prevent the enemy from reaching its goal. In this research, a multi-period dynamic interdiction problem in fuzzy conditions is investigated in order to help military decision-makers and commanders to choose an appropriate strategy. In this problem, the defense forces in the role of interdictor try to minimize the maximum flow during the T period so that at each stage the interdictor and the enemy are fully aware of the performance of the other side. Edge capacities in this model are considered as fuzzy variables. To solve the proposed model, first, the fuzzy dynamic interdiction problem is transformed into the deterministic dynamic interdiction problem with the help of the concepts of credibility measure and chance constraint programming. Then, by creating the crisp two-level problem created by duality, it is transformed into a single-level problem, and then it is solved by using the generalization of Banders decomposition algorithm. Finally, the validity of the problem is evaluated by providing a numerical sample.
Keywords
Network interdiction
Fuzzy theory
Credibility Value
Benders decomposition
  • Abdolahzadeh, A., Aman, M., & Tayyebi, J. (2020). Minimum st-cut interdiction problem. Computers & Industrial Engineering, 148: 106708.
  • Afshari Rad, M., & Kakhki, H. T. (2013). Maximum dynamic network flow interdiction problem: New formulation and solution procedures. Computers and Industrial Engineering, 65 (4): 531-536.
  • Assimakopoulos, N. (1987). A network interdiction model for hospital infection control. Computers in Biology and Medicine, 17 (6): 413-422.
  • Bingol, L. (2001). A Lagrangian Heuristic for Solving Network Interdiction Problem, Master’s thesis, Naval Postgraduate School.
  • Carlyle, W. M., Royset, J. O., & Wood, R. K. (2008). Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks, 52(4): 256-270.
  • Crainic, T. G., Frangioni, A., & Gendron, B. (2001). Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Applied Mathematics, 112(1–3): 73-99.
  • Forghani, A., Dehghanian, F., Salari, M., & Ghiami, Y. (2020). A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities. Computers & Operations Research, 114, 104831.
  • Gutfraind, A. (2011). New Models of Interdiction in Networked Systems on JSTOR. Military Operations Research Society, 44 (2): 25-27.
  • Li, X., & Liu, B. (2006). A Sufficient and necessary condition for credibility measures. International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems, 14(5): 527-535.
  • Lim, C., & Smith, J. C. (2007). Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Transactions (Institute of Industrial Engineers), 39(1): 15-26.
  • Liu, B. (2006). A survey of credibility theory. Fuzzy Optimization and Decision Making, 5(4): 387-408..
  • Liu, B., & Liu, Y. K. (2002). Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems, 10(4): 445-450.
  • Liu, D. B. (2007). Uncertainty Theory, Springer, Berlin, Heidelberg.
  • Liu, Y. K., & Gao, J. (2011). The independence of fuzzy variables with applications to fuzzy random optimization. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 15 (supp02): 1-20.
  • Lunday, B. J., & Sherali, H. D. (2010). A dynamic network interdiction problem. Informatica, 21(4): 553-574.
  • Lunday, B. J., & Sherali, H. D. (2012). Network interdiction to minimize the maximum probability of evasion with synergy between applied resources. Annals of Operations Research, 196(1): 411-442.
  • Malaviya, A., Rainwater, C., & Sharkey, T. (2012). Multi-period network interdiction problems with applications to city-level drug enforcement. IIE Transactions (Institute of Industrial Engineers), 44(5): 368-380.
  • Phillips, C. A. (1993). The network inhibition problem. Proceedings of the Annual ACM Symposium on Theory of Computing, 776-785.
  • Salmeron, J., Wood, K., & Baldick, R. (2004). Analysis of electric grid security under terrorist threat. IEEE Transactions on Power Systems, 19(2).
  • Soleimani-Alyar, M., & Ghaffari-Hadigheh, A. (2018). Dynamic Network Interdiction Problem with Uncertain Data. International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems, 26 (2): 327-342.
  • Wood, R. K. (1993). Deterministic network interdiction. Mathematical and Computer Modelling, 17 (2): 1–18.
  • Xiao, K., Zhu, C., Zhang, W., & Wei, X. (2020). The Bi-Objective Shortest Path Network Interdiction Problem: Subgraph Algorithm and Saturation Property. IEEE Access, 8, 146535–146547.
  • Zadeh, L. A. (1965). Fuzzy sets. Information and Control, 8(3): 338-353.
  • Zadeh, L. A. (1978). Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems, 1(1): 3-28.