Hybrid algorithms for enhanced efficiency and scalability of network-based tri-level interdiction models

This study focuses on optimizing resilience strategies for interdependent infrastructure networks (e.g., electric power, water supply, transportation system) against intelligent attacks. We formulate this problem as a tri-level defender-attacker-defender (DAD) model, which is known for its computational complexity. To address this challenge, we propose two novel hybrid decomposition-based algorithms: the hybrid Benders decomposition-based (HBD) algorithm and the hybrid set covering-based (HSC) algorithm. These algorithms efficiently solve the nested subproblems (master problem and subproblem) of the tri-level DAD formulation, incorporating metaheuristic algorithms for improved performance. The proposed algorithms are applied to a tri-level protection-interdiction-restoration model to optimize network resilience. Two case studies are used to evaluate the effectiveness of the solution techniques: (i) An interdependent system of water, gas, and power networks with 125 nodes and 164 links, and (ii) A simulated system of two networks with 252 nodes and 507 links. Our results demonstrate that both hybrid algorithms offer high-quality solutions with significantly improved computational efficiency compared to the existing exact solution method based on the set covering approach. In our comparison across different case studies and budget scenarios, we find that for higher budget scenarios, the HBD algorithm outperforms the HSC algorithm and is more computationally efficient. For lower budget scenarios, the performance of both algorithms is similar, with the HSC algorithm showing slightly better performance in terms of computational speed. Both algorithms show clear advantages over the set covering (CD) approach, particularly when available budget grows. This study highlights that the choice between the HBD and HSC algorithms depends on both the case study size and available budget, with the HBD algorithm being preferable in higher budget scenarios and the HSC algorithm being slightly more efficient in lower budget scenarios.