Power grid vulnerability, new models, algorithms and computing Daniel Bienstock Abhinav Verma ColumbiaUniversity,NewYork February, 2009 DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 1/44 Talk Outline Lossless power flows Solving the N-k problem A better model for the N-k problem DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 2/44 Power flow model - lossless model We are given a network with nodes N (“buses”) and arcs A (“lines”): A set of G of supply nodes (the “generators”); each generator i has 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) a parameter x . ij Basic problem: operate network so as to maximize amount of delivered power DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 3/44 Power flow model - lossless model We are given a network with nodes N (“buses”) and arcs A (“lines”): A set of G of supply nodes (the “generators”); each generator i has 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) a parameter x . ij Basic problem: operate network so as to maximize amount of delivered power DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 3/44 Power flow model - lossless model We are given a network with nodes N (“buses”) and arcs A (“lines”): A set of G of supply nodes (the “generators”); each generator i has 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) a parameter x . ij Basic problem: operate network so as to maximize amount of delivered power DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 3/44 Power flow model - lossless model We are given a network with nodes N (“buses”) and arcs A (“lines”): A set of G of supply nodes (the “generators”); each generator i has 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) a parameter x . ij Basic problem: operate network so as to maximize amount of delivered power DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 3/44 Feasible power flows Suppose we choose an output level b > 0 for each generator i, and i a demand level −b > 0 for each load i. i Write b = 0 for each other node i. i A power flow is a solution f, θ to: P P P f − f = b , for all i (so must assume b = 0) ij ij ij ji i i i x f − sin(θ − θ ) = 0, for all (i,j), (physics) ij ij i j | θ −θ | ≤ π (“stability”) i j 2 A difficult system? DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 4/44 Feasible power flows Suppose we choose an output level b > 0 for each generator i, and i a demand level −b > 0 for each load i. i Write b = 0 for each other node i. i A power flow is a solution f, θ to: P P P f − f = b , for all i (so must assume b = 0) ij ij ij ji i i i x f − sin(θ − θ ) = 0, for all (i,j), (physics) ij ij i j | θ −θ | ≤ π (“stability”) i j 2 A difficult system? DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 4/44 Feasible power flows Suppose we choose an output level b > 0 for each generator i, and i a demand level −b > 0 for each load i. i Write b = 0 for each other node i. i A power flow is a solution f, θ to: P P P f − f = b , for all i (so must assume b = 0) ij ij ij ji i i i x f − sin(θ − θ ) = 0, for all (i,j), (physics) ij ij i j | θ −θ | ≤ π (“stability”) i j 2 A difficult system? DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 4/44 Feasible power flows Suppose we choose an output level b > 0 for each generator i, and i a demand level −b > 0 for each load i. i Write b = 0 for each other node i. i A power flow is a solution f, θ to: P P P f − f = b , for all i (so must assume b = 0) ij ij ij ji i i i x f − sin(θ − θ ) = 0, for all (i,j), (physics) ij ij i j | θ −θ | ≤ π (“stability”) i j 2 A difficult system? DanielBienstockAbhinavVerma(ColumbPiaoUwneirvgerrisditvy,uNlneewraYboilrikty),newmodels,algorithmsandcompFuetbinrugary,2009 4/44