Power grid vulnerability, new models, algorithms and computing Daniel Bienstock Abhinav Verma ColumbiaUniversity,NewYork ICS09 DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 1/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 The N-k problem in power grids Given a power grid modeled by a network, delete a small set of arcs, such that in the resulting network all feasible flows have small throughput Used to model “natural” blackouts “Small” throughput: we satisfy less than some amount Dmin of total demand “Small” set of arcs = very small Delete 1 arc = the “N-1” problem Of interest: delete k = 2,3,4,... edges Naive enumeration blows up DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 2/57 Linear power flow model We are given a network G with: A set of S of supply nodes (the “generators”); for each generator i an “operating range” 0 ≤ SL ≤ SU, i i A set D of demand nodes (the “loads”); for each load i a “maximum demand” 0 ≤ Dmax. i For each arc (i,j) values x and u . ij ij DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 3/57 Linear power flow model We are given a network G with: A set of S of supply nodes (the “generators”); for each generator i an “operating range” 0 ≤ SL ≤ SU, i i A set D of demand nodes (the “loads”); for each load i a “maximum demand” 0 ≤ Dmax. i For each arc (i,j) values x and u . ij ij DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcomputing ICS09 3/57