IDENTIFYING THE MOST CRITICAL p-NODES IN ARC CAPACITATED s-t FLOW NETWORKS UNDER LOCAL ATTACK CONSTRAINTS

Abstract

This paper presents a novel network interdiction problem, the optimal removal of non-adjacent p-nodes for s-t flow networks such that the blocked flow between specific sources and destinations is maximized. First, the transformed model that modifies the recent best-performing arc disrupted model of the literature is presented to exactly address the studied problem here. Second, for the sake of computational improvements, a reduced model (i.e., a model having significantly reducing constraints-and-variables) specifically designed for this problem is introduced. The superiority of the reduced model over the transformed model was observed on the well-known relatively large size network. In particular, it was observed that the reduced formulation returned the best non-adjacent node combinations for all p values within a reasonable period of time, whereas the transformed model could not return optimal values for many p values even in three hour time frame.

Keywords

• Optimization
• critical node detection
• network interdiction
• local protection
• arc-capacitated flow network

YEREL SALDIRI KISITLAMALARI ALTINDA AYRIT KAPASİTELİ s-t AKIŞ AĞLARINDA EN KRİTİK p-DÜĞÜMLERİNİN BELİRLENMESİ

Öz

Bu makale, belirli kaynaklar ve hedefler arasındaki engellenen akışı en büyükleyecek şekilde s-t akış ağları için bitişik olmayan p-düğümlerinin optimum şekilde kaldırılmasını içeren yeni bir ağ kırılma problemi sunmaktadır. İlk olarak, literatürdeki en iyi performans gösteren ayrıt kırılması modelini değiştiren dönüştürülmüş model, burada incelenen problemi tam olarak ele almak için sunulmuştur. İkinci olarak, hesaplama iyileştirmeleri uğruna, bu problem için özel olarak tasarlanmış indirgenmiş bir model (yani, önemli ölçüde azaltılmış kısıtlamalara ve değişkenlere sahip model) tanıtılmıştır. İndirgenmiş modelin dönüştürülmüş modele göre üstünlüğü, iyi bilinen nispeten büyük boyutlu ulaşım ağı üzerinde gözlemlenmiştir. Özellikle, indirgenmiş formülasyonun tüm p değerleri için en iyi bitişik olmayan düğüm kombinasyonlarını makul bir süre içinde döndürdüğü, dönüştürülmüş modelin ise birçok p değeri için üç-saatlik zaman diliminde dahi optimum değerleri döndüremediği gözlemlenmiştir.

Anahtar Kelimeler

• Optimizasyon
• kritik düğüm tespiti
• ağ kırılma
• yerel koruma
• ayrıt kapasiteli akış ağı

Kaynakça

1. 1. Sheffi, Y.. “Urban Transportation Networks”, Pretince-Hall, Englewoods Cliffs, 1985.
2. 2. Klein, M.. “A primal method for minimal cost flows with applications to the assignment and transportation problems”, Management Science 14(3): 205–220, 1967.
3. 3. Wood, R.K., 1993. “Deterministic network interdiction”, Mathematical Computational Modelling 17: 1–18, 1993.
4. 4. Karakose, G. and McGarvey, R.G.. “Optimal K-node disruption on a node-capacitated network”, Optimization Letters 13(4): 695-715, 2019.
5. 5. Karakose, G. and McGarvey, R.G.. “Capacitated path-aggregation constraint model for arc disruption in networks”, Transportation Research Part E: Logistics and Transportation Review 109: 225-238, 2018.
6. 6. Karakose, G. and McGarvey, R.G.. “Optimal detection of critical nodes: Improvements to model structure and performance”, Networks and Spatial Economics 19: 1- 26, 2019.
7. 7. Karakose, G. and McGarvey, R.G.. “Node-securing connectivity-based model to reduce infection spread in contaminated networks”, Computers & Industrial Engineering 115: 512-519, 2018.
8. 8. Israeli, E., Wood, R.K. “Shortest-path network interdiction”, Networks 40(2): 97–111, 2002.

9. 9. Jin, J.G., Lu, L., Sun, L. and Yin, J.. “Optimal allocation of protective resources in urban rail transit networks against intentional attacks”, Transportation Research Part E: Logistics and Transportation Review 84: 73-87, 2015.
10. 10. Veremyev, A., Boginski, V. and Pasiliao, E.L.. “Exact identification of critical nodes in sparse networks via new compact formulations”, Optimization Letters 8: 1245-1259, 2014.
11. 11. Matisziw, T.C. and Murray, A.T.. “Modeling s–t path availability to support disaster vulnerability assessment of network infrastructure”, Computers & Operations Research, 36(1): 16-26, 2009.
12. 12. Myung, Y.S. and Kim, H.J.. “A cutting plane algorithm for computing k-edge survivability of a network”, European Journal of Operational Research, 156(3): 579-589,2004.
13. 13. Transportation Networks for Research Core Team. Transportation Networks for Research. https://github.com/bstabler/TransportationNetworks. Yayın Tarihi Mayıs 1, 2016. Erişim Tarihi Temmuz 29, 2023.