Optimal power grid protection through a defender-attacker-defender model

Power grid vulnerability is a major concern of our society, and its protection problem is often formulated as a tri-level defender-attacker-defender model. However, this tri-level problem is computationally challenging. In this paper, we design and implement a Column-and-Constraint Generation algorithm to derive its optimal solutions. Numerical results on an IEEE system show that: (i) the developed algorithm identifies optimal solutions in a reasonable time, which significantly outperforms the existing exact algorithm; (ii) the attack solution obtained through solving the attacker-defender model does not lead to the optimal protection plan in general; and (iii) protection using the optimal solution from the defender-attacker-defender model always improves the grid survivability under contingencies. The proposed model and algorithm can be easily modified to accommodate for other critical infrastructure network protection problems. (C) 2013 Elsevier Ltd. All rights reserved.