This work addresses the problem of identifying the set of nodes in a power network critical to system operation. Formally, the CNA problem is the problem of identifying a minimum cardinality set of nodes to target in a power network in order to reduce throughput by a given factor. Since the defender may reroute flows in an attempt to restore throughput, the attack must anticipate and defeat this possibility. We develop here an algorithm to solve this problem. In our approach we model the problem as a bi-level optimization problem where the master problem attempts different attack combinations and the sub-problem responds with the best routing. The optimization problems that result from such a framework are mixed integer programs (MIPs), which we solve in our implementation using IBM CPLEX. The algorithm has been tested on several benchmark networks and appears to perform well. We have also developed variants that can be used for determining optimal restoration configuration post damage on large networks (4000 nodes, 8000 links) and for modeling propagation of failures after the initial attack. We report on computational experiments with these variants as well.

Date Published: 12 May 2016
PDF: 15 pages
Proc. SPIE 9850, Machine Intelligence and Bio-inspired Computation: Theory and Applications X, 985005 (12 May 2016); doi: 10.1117/12.2223499

Published in SPIE Proceedings Vol. 9850:
Machine Intelligence and Bio-inspired Computation: Theory and Applications X
Misty Blowers; Jonathan Williams; Russell D. Hall, Editor(s)