A decomposition approach for solving tri-level defender-attacker-defender problems

摘要

Network-based systems widely appear in different service, community, industrial, and economic systems such as electric power, water supply, transportation, and telecommunication networks. Due to the significant role of such systems in society, it is essential to have an effective plan to enhance the resilience of infrastructure networks against disruption (e.g., natural disasters, malevolent attacks, or operational failures). In relation to the concept of resilience, two relevant questions arise: (ⅰ) how does performance degrade after a disruption, or what is the vulnerability of the system? and (ⅱ) how rapid does the disrupted system return to the desired performance level, or how can we characterize the system's recoverability? To enhance the resilience of a system against disruption, we address simultaneous actions of vulnerability reduction and recoverability enhancement through interdiction model, particularly defender-attacker-defender (DAD) model. However, the proposed model is computationally challenging to solve. To deal with this issue, we design a decomposition-based solution algorithm as a general framework to optimally solve tri-level DAD models in more efficiently. The proposed solution technique is demonstrated with the existing DAD model, namely a tri-level protection-interdiction-restoration model. To define the critical components subject to protection and disruption, an efficient clustering technique is applied which results in generating three sets of candidate components based on three centrality measures. We represent an illustrative case study based on the system of interdependent infrastructure networks in Shelby County, TN, for which we solve the model and assess the computational results for each set of candidate components. The results indicate that the proposed solution algorithm substantially outperforms the traditional covering decomposition method with regard to computational complexity, particularly for the higher budget scenarios. Finally, we compare and analyze the results of the existing interdiction model, the protection-interdiction-restoration formulation represented by M-Ⅰ, with a new protection-interdiction-counteraction model, denoted by M-Ⅱ, in which the restoration level is not considered. Results suggest that although M-Ⅰ is a comprehensive interdiction model relative to M-Ⅱ, it suffers substantially from computational complexity. Therefore, there exists a tradeoff between employing a more comprehensive model with higher computational complexity and neglecting the recovery process with the interdiction model.