Communication Line Protection Against Sabotages Using Dynamic Minimum Cut Interdiction

Document Type : Original Article

Authors

1 Department of Mathematics, Faculty of Science, University of Birjand, Iran

2 Department of Mathematics, Faculty of Mathematics and Statistics, University of Birjand, Birjand, Iran

3 Department of Industrial Engineering, Birjand University of Technology, Birjand, Ira

Abstract

In ground wars, one of the enemy's main goals is to monitor communication networks and to interrupt the force and equipment lines. For this purpose, the optimal approach is to disconnect routes on a minimum cut. This is possible by air, missile, and artillery attacks, as well as the destruction of bridges and roads. On the other hand, the defense forces seek to exploit maximally the available resources and facilities to interdict the enemy reaching this goal. In this paper, we model this problem from the viewpoint of defense forces in the form of a bi-level network interdiction problem. Due to the inherent complexity and nature of the problem, we solve it using the Bender's decomposition approach. Finally, we establish the validity of the model by a practical example.

Keywords

References

  1. Bigdeli, H.; Tayyebi, J.; Partovi, M. “War Game and Mathematical Models”; First Edition, Dafous Publications (In Persian).##
  2. Afshari Rad, M. “Maximum Flow Interdiction Problem In Network: New Solutions and Generalization to Dynamic Networks”; Doctoral Dissertation, Faculty of Mathematical Sciences, Ferdowsi University, 2012, (In Persian).##
  3. Steinrauf, R. L. “Network Interdiction Model, Master Thesis”, Monterey, California, 1991.##
  4. Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. “Network Flows, Theory, Algorithms, and Applications”; 1st Prentice Hall, New Jersey, 1993.##
  5. Ford, L. R.; Fulkerson, D. R. “Flows in Networks”; Princeton University Press, New Jersey, 1962.##
  6. Bracken, J.; McGill, J. T. “Mathematical Programs with Optimization Problems in the Constraints”; Oper. Res.
    1973, 21, 37-44.##
  7. Candler, W.; Norton, R. “Multi-level Programming and Development Policy”; The World Bank, 1977.##
  8. Bard, J. “Practical Bi-level Optimization:  Algorithms and Applications”; Kluwer Academic Publishers, USA, 1998.##
  9. Wollmer, R. D. “Removing arcs from a Network”; J. Oper. Res. 1964, 12, 934-940.##
  10. McMastres, A.W.; Mustin, T. M. “Optimal Interdiction of a Supply Network”; Nav. Res. Log. Quar. 1970,
    17(3), 261-268.##
  11. Wood, R. K. “Deterministic Network Interdiction Problem”; Math. Comput. Modell. 1993, 17, 1-18.##
  12. Kennedy, K. T.; Deckro, R. F.; Moore, J. T.; Hopkinson, K. M. “Nodal Interdiction”; Math. Comput. Model 2011, 54
    (11-12), 3116–3125.##
  13. Lunday, B. J.; Sherali, H. D. “A Dynamic Network Interdiction Problem”; Inf. 2010, 21, 553-574.##‏
  14. Rad, M. A.; Kakhki, H. T. “Maximum Dynamic Network Flow Interdiction Problem: New Formulation and Solution Procedures”; Comput. Ind. Eng. 2013, 65, 531-536.##
  15. Ratliff, H. D.; Sicilia, G. T.; Lubore, S. H. “ Finding the Most Vital Links in Flow Networks”; Manage. Sci. 1975, 21, 531-539.##
  16. Akgün, İ.; Tansel, B. Ç.; Wood, R. K. “The Multi-Terminal Maximum-Flow Network-Interdiction Problem”; Eur. J. Oper. Res. 2011, 211, 241–251.##
  17. Lim, C.; Smith, J. C. “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems”; IIE Trans. 2007, 39, 15-26.##
  18. Mohammadi, A.; Tayyebi, J. “Maximum Capacity Path Interdiction Problem with Fixed Costs”; Asia-Pac. J. Oper. Res. 2019, 36, 1950018.##
  19. Ramirez-marquez, E.; Daniel, E.; Salazar, A.; Claudio, M.; Rocco, S. “Bi and Tri Objective Optimization in the Deterministic Network Interdiction Problem”; Rel. Eng. Syst. Saf. 2010, 95, 887–96.##
  20. Chen, Y.; Cheng, G.; Shenghan, Yu. “Bi-Objective Optimization Models for Network Interdiction”; RAIRO Oper. Res. 2019, 53, 461–472.##
  21. Lim, C.; Smith, J. “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems”; IIE Trans. 2007, 39,15–26.##
  22. Smith, J. C.; Yongjia, S. “A Survey of Network Interdiction Models and Algorithms”; Eur. J. Oper. Res. 2020, 283, 797-811.##
  23. Bigdeli, H.; Hassanpour, H.; Tayyebi, J. “The Optimistic and Pessimistic Solutions of Single and Multiobjective Matrix Games with Fuzzy Payoffs and Analysis of some of Military Problems”; Adv. Defence Sci. & Technol. 2016, 2, 133-145 (In Persian).##
  24. Bigdeli, H. “Quadratic Programming Method for Choosing Optimal Decision in Fuzzy and Complex Environment of Battle Scenario”; Adv. Defence Sci. & Technol. 2020, 11, 238-231.##
  25. Ben-Ayed, O.; Boyce, D. E.; Blair, C. E. “A General Bilevel Linear Programming Formulation of the Network Design Problem”; Trans. Res. Part B 1988, 22, 311-318.##
  26. Washburn, A. R. “Two-Person Zero-Sum Games”; Springer Edition 4, 2014.##

Files

History

  • Receive Date: 18 August 2020
  • Revise Date: 21 December 2020
  • Accept Date: 29 December 2020

Share

How to cite

Statistics