Keywords

1 Introduction

Since the Industrial Age, human being has created many networks, which are tightly related to our daily life. These networks could be categorized as physical or engineered networks, information networks, biological networks, cognitive and semantic networks, and social networks, which for example include but not limited to electrical network, computer network, biological network, artificial neural network, social network, business networking, radio network, telecommunications network, television network.

As the concept of network reaches every aspects of the human society, the new discipline of network theory has been developed to study their interconnection phenomena, and to explore common principles, algorithms, and tools that govern network behavior. Several parameters such as density, size, average degree, average path length, diameter of a network, clustering coefficient and connectedness, which are rooted from graph theory, have been utilized to analyze the properties and characteristics of the network. Based on different parameters, generic network could be described by different network models, such as small world model, scale-free network model, preferential attachment model and SIR model, etc. The small world model, scale-free network model, and preferential attachment model are randomly generated graphs, while the first two observe the degree distribution fitted with a power law distribution. The small-world network is the one which is studied mostly and widely since it has the small-world properties which are found in many real-world phenomena, including road maps, food chains, electric power grids, metabolite processing networks, networks of brain neurons, voter networks, telephone call graphs, and social influence networks. With this property, networks are likely to have cliques, quasi-cliques, and/or clubs, meaning high connectivity between any two nodes within sub-networks due to a high clustering coefficient, and at the meanwhile most pairs of nodes will be connected by at least one short path via some “hub” nodes with a high degree.

Among those example networks, electricity network or power grid has been on the table drawing lots of eyeballs, and one reason is that it is the oldest and most traditional of the various mega structures. The electricity network has been evolving from several close-circuit systems within some particular geographic areas, where all energy was produced near the end users which demand that energy. During the past decades the power infrastructure has evolved into what many experts consider the largest and most complex system of the technological age. Geographically, the North American power grid forms a network of over 6100 generation plants, over 365,000 mile of high-voltage lines, over 6 million mile of low-voltage lines, and over 45,000 transformers that are continuously regulated by sophisticated control equipments. Consisting of millions of miles of lines operated by over 500 companies, the Continental US power grid is one of largest electricity infrastructure in the world, and it is a complex network system of power plants and transmission lines which are independently owned and operated. However, despite of the advance in technology and design of the electrical grid, its power delivery infrastructures suffer aging issue across the whole world. Aged equipments and facilities have higher failure rates and subject to higher maintenance and further repair/restoration costs; aged areas require additional substation sites more than available to meet the demand of ever growing customers; problems caused by aged equipments and facilities, obsolete system layouts, and modern deregulated electricity distribution patterns could not be effectively addressed by traditional concepts, planning, engineering, and operation of power network systems.

The other reason why electricity network is so important is that it recently attracted attention from the House Foreign Affairs Committee about its security issue. Delivery of electricity power is critical to any country’s economy and security. As a result of the recent deregulation of power generation and transmission, about one-half of all domestic generation is now sold over ever-increasing distances on the wholesale market before it is delivered to customers, and consequently the power grid is witnessing power flows in unprecedented magnitudes and directions. Therefore surges in power lines can cause massive network failures and permanent damage to multimillion dollar equipment in power generation plants.

The electrical network has its own characteristics to make itself special than other networks. First, it has to observe the following physical laws: (1)Kirchhoff’s current law: The sum of all currents entering a node is equal to the sum of all currents leaving the node; (2) Kirchhoff’s voltage law: The directed sum of the electrical potential differences around a loop must be zero; (3) Ohm’s law: The voltage across a resistor is equal to the product of the resistance and the current flowing through it; (4) Norton’s theorem: Any network of voltage or current sources and resistors is electrically equivalent to an ideal current source in parallel with a single resistor; and (5) Th\acute{e}venin’s theorem: Any network of voltage or current sources and resistors is electrically equivalent to a single voltage source in series with a single resistor. Second, as the modern trends in the twenty first century, the electric utility industry seeks to take advantage of novel approaches to meet growing energy demand with everything interconnected. Within this kind of wide area synchronous grid, alternating current (AC) with frequencies synchronized can be transmitted throughout the wide area, connecting a large number of electricity generators and consumers. However, in such a synchronous grid, all the generators run not only at the same speed but also at the same phase, and generation and consumption must be balanced across the entire grid. Hence, a single failure in a local area could cause power flow to re-route over transmission lines of insufficient capacity, which may result in further failures in other parts of the grid, in other word, the possibility of cascading failure and widespread power outage.

An electricity blackout is the situation where there is a total loss of power to a relatively wide area, and it is the most severe form of power outage. There are many causes of blackout in an electricity network, including faults at power plant stations, damage to power lines, a short circuit, or the overloading of electricity transmission systems. Blackouts are especially difficult to recover quickly, and may last from a few hours to a few weeks depending on the nature of the blackout and the configuration of the electrical network. Restoring power after a wide area blackout needs to be done with the help of power from other grid. In the extreme case where there is total absence of grid power, a so-called black start needs to be performed to bootstrap the power grid into operation, which depends greatly on local circumstances and operational policies. Since localized “power islands” are progressively coupled together, in order to maintain supply frequencies within tolerable limits during this process, demand must be reconnected at the same pace that generation is restored, requiring close coordination between power stations, transmission, and distribution organizations.

In the USA, the system’s vulnerability to physical disruptions from natural disasters and other causes has long been studied. However, this vulnerability has increased in recent years because infrastructure has not expanded as quickly as demand has, thereby reducing the system’s tolerance against deteriorated, failed, or unavailable system components. During the most severe form of power outage, blackout which is a total loss of power to a relatively wide area, tremendous societal consequences and substantial economical loss would be incurred. The possible causes for blackout may be faults at power stations, damage to power lines, a short circuit, or the overloading; the entire procedure could be so complicated due to the cascading phenomenon which is resulted from the self-organizing dynamical forces driving the system. Moreover, the threat of human attacks on the system has become more serious, too. Therefore, the methodology and algorithms proposed here could have rich applications used in daily operation management, emergency strategy, and expansion planning for power grid.

2 Blackout Analysis

The US electric power system has been serving this nation for more than a century ever since Thomas Edison designed and built the world’s first central power station in New York City in 1882. Today, however, the aged but scattered infrastructure combined with an increasing demand in domestic electricity consumption, which is extremely vulnerable to even small scale of unintentional outage failure (say nothing of intentional contingency), has forced us to critically examine the condition and health of the nation’s electrical systems before it could be outdated and unprepared to deliver reliable electricity to the consumers. Therefore, there is a lot of academic research which aims at predicting the occurrence of blackout and mitigating the impact of blackout by designing and operating power systems in the way that the power grid system could tolerate with emergency events such as the loss of power transmission route, changing in the demand and generation patterns, etc.

2.1 Probabilistic and Reliability Model

Instead of considering the power grid as an integrated complex system in a macroscopic way, some researchers have begun to use probabilistic and reliability model to describe the system in the microscopic way. Most of the papers on probabilistic model related to power grid blackout are contributed by Ian Dobson and his co-authors, and there are mainly three models they developed and/or largely used to explore the aspects of blackouts. The CASCADE and branching process models are used to represent the dynamic features of the cascading failure in a tractable way, while the OPA model describes the power transmission system in an abstract way.

2.1.1 Cascading Property

The cascading failure is a built-in property of a power grid system in which the failure of a component can trigger the failure of successive components by load-shifting. Cascading is the key factor for large scale power blackout, and it deserves the close attention paid from many researchers:

  • Distribution of Interval Between Blackouts Different papers have made controversary conclusions about the distribution of the time between blackouts. Some [17, 39, 100] conclude with exponential tail or similar, while others think about negative binomial [88] or Poisson distribution [50]. The probability distribution of the time between blackouts is at least determined by the probability of the trigger, and the time between blackouts is a mixture of gamma distributions [39].

  • Distribution of Blackout Size The question people would mostly ask when hearing of power blackout is about the size and its distribution. The exponential distribution would be the most possible answer, which is easy to understand. Analysis of North American blackout statistics from NERC (North American Electric Reliability Council) Disturbance Analysis Working Group (DAWG) database (http://www.nerc.com) show, that it has an approximate power-law region with an exponent between -1 and -2 ([5, 17]). The power-law implies that blackouts can occur in all sizes and most importantly at all places. Different power systems in different countries ([50, 54, 99]) show roughly similar forms of blackout size distribution in power-law dependence. Dobson and his coworkers have some papers ([30, 55]) estimating the average propagation of failures and the size of the initial disturbance and to predict the distribution of blackout size.

  • Self-Organization Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning. Many scholars have argued that, through computer simulation and historical data, power grids are self-organized critical systems, in which the evolving process is quite complicated. Based on a simple model of DC load flow and LP dispatch and NERC data on North American blackouts, ([17, 19]), the dynamics of blackouts have some features of self-organized critical systems [88].

  • Criticality As the load increases, the average blackout size increases very slowly, until, at a loading called the critical loading, there is a sharp change and average blackout size starts increasing much more quickly ([18, 52, 73]).

2.1.2 CASCADE Model

The CASCADE model consists of finitely large number of components with a failure threshold, an initial system loading, a disturbance over certain component(s), and the addition loading on component caused by failure of other component(s).

In the CASCADE model, there are n identical components with random initial loading, and for each component the minimum and maximum initial loading are \({L}^{min}\) and \({L}^{max}\), respectively. Component j is assumed to have an initial loading of \(L \in [{L}^{min},{L}^{max}]\) with a uniform distribution, and \({L}_{j},j = 1,2,\ldots,n\) are identically distributed. They normalized the initial load by,

$${\mathcal{l}}_{j} = \frac{{L}_{j} - {L}^{min}} {{L}^{max} - {L}^{min}}$$

therefore \({\mathcal{l}}_{j}\) is a random variable with a standard uniform distribution, \({\mathcal{l}}_{j} = 1\) being the failure load.

To begin cascade process, they also assume that there is an initial disturbance D on each component (D could be 0 for certain components), and failures caused by D on some components would add an extra load P on other components resulting in further failures as a cascading process. P and D can be normalized as

$$\begin{array}{rcl} p& =& \frac{P} {{L}^{max} - {L}^{min}} \\ d& =& \frac{D + {L}^{max} - {L}^{fail}} {{L}^{max} - {L}^{fail}} \\ \end{array}$$

The distribution for the total number S of failed components is

$$P[S = r] = \left ({ n \atop r} \right )d{(d + rp)}^{r-1}{(1 - d - rp)}^{n-r}$$

When considering the interaction mechanism among individual components, they proposed an algorithm for normalized CASCADE with k interactions:

  1. 0.

    Set all n components with initial load \({\mathcal{l}}_{1},{\mathcal{l}}_{2},\ldots,{\mathcal{l}}_{n}\) iid from standard uniform distribution.

  2. 1.

    Sample the n components k times independently and uniformly with replacement, add the initial disturbance d to the load of the sampled components, and set the stage index i to zero.

  3. 2.

    Test each components which are not marked as failed before sampling in the previous step. If component j is not marked as failed and its load \({l}_{j} > 1\), then mark it as failed. Let M i be the number of total failed components in stage i.

  4. 3.

    Including those M i components, sample the n components k times independently and uniformly with replacement, and add p to the load of the sampled components.

  5. 4.

    Increase the stage index by 1 and go to step 2.

2.1.3 Branching Process Model

By introducing some general processing models such as Galton-Watson branching process with generalized Poisson distribution, these scholars could approximate the CASCADE model with simplified mathematical model so that each step of the cascading failure propagation could be calculated. The basic idea behind the Galton-Watson branching process is that the failure on each component in each stage will independently result in future failures in the next stage associated with a probability distribution, and it could be represented in mathematics as following:

$${M}_{i+1} = {M}_{i+1}^{(1)} + {M}_{ i+1}^{(2)} + \cdots + {M}_{ i+1}^{({M}_{i})}$$

where \({M}_{i+1}^{k}\) is identically independent by assumption and defined as the failures caused by kth component failure in stage i, so the total number of failures is

$$M =\sum\limits_{k=0}^{\infty }{M}_{ k}$$

In addition to the above model, with the assumption that each component failure would cause further failures according to a Poisson distribution of mean \(\lambda \), the branching process could be modeled as a transient discrete time Markov process with its behavior governed by the parameter \(\lambda \). Therefore, the total number of failures becomes

$$P[M = r] = {(r\lambda )}^{r-1}\frac{{e}^{-r\lambda }} {r!},\quad 0 \leq \lambda \leq 1$$

They also have a high-level version of probabilistic model of the cascading process which utilizes a continuous state branching process [55]. With all these models, they propose some statistical estimators to measure the extent to which the load shedding is propagated.

However, this approximation can only work in a system with many components and many component interactions so that series of failures propagating in parallel can be assumed not to interact, and it cannot reflect the mechanism and complexities of loading-dependent cascading failure which does exist in real power network system.

2.2 Simulation and Complex System Model

In order to dynamically predict the behavior of the gigantic power grid under various circumstances, with the help of advanced information technology, people can use simulation model to not only better understand the entire power grid itself but to obtain some experimental results in a timely manner as well. Most of these researches involves complex system analysis with characteristics of cascading; therefore they are related to power blackout analysis since that power grid is usually treated as a complex network, cascading is a universal phenomenon on power grid.

The complex system or networks has already drew a lot of attraction from researchers in multiple files, even before the power security issue has been exposed to public attention. Newman [74] and Albert and Barab\acute{a}si [2] review the recent advances in the field of complex networks, including modeling the network and predicting its dynamic behavior. They discussed several main network models with network topology and network’s robustness against failures and attacks. Albert, Jeong, and Barab\acute{a}si [83] especially focused on the tolerance against errors or attacks among different types of complex networks. Watts and Strogatz [98] studies the dynamics of “small-world” networks, where they explicitly claimed that the power grid of the Western United States are in such category.

In the field of cascading failure simulation, various methods and models are proposed to capture the cascading phenomenon, and most of them focus on certain aspects of cascading which could be represented by successive static models, while most of which are related to such as static line overloading at the level of DC or AC load flow. There are several papers [7, 12, 22, 23, 45, 56, 85, 92] concentrating on hidden failures with protection control and operator reaction.

Due to the difficulties and complexities of modeling and the heavy computation burden, dynamic analysis such as self-organization during blackout has not been well studied. However, it is critical to study, in more detail, the transient status of the evolving power grid that is continually upgrading to couple with the changing load and generation demand [63, 94]. Simulation such as the OPA could help to better understand transient reliability [19, 65], and identify some high-risk cascades as well [23, 24, 34, 84].

Besides those researches, there is one which caught a lot of eyeballs, even the ones from Larry M. Wortzel, a military strategist and China specialist. On March 10, 2009, he presented the US House on Foreign Affairs committee that it should be concerned on how to attack a small US power grid subnetwork in a way that would cause a cascading failure of the entire US grid [101], and his statement is based from a paper published [96] on the journal of Safety Science. The purpose of the research, explained by the author Mr. Jianwei Wang and his colleagues from Dalian University of Technology, China, is to try to find ways to enhance the stability of power grids by exploring potential vulnerabilities.

In all the other studies cited below, the load on a node (or an edge) was generally estimated by its degree or betweenness and the redistribution load was usually forwarded following the shortest path. Wang proposed a new measure to assign the initial load of a node and to redistribute load among nodes after attacking, in order to reduce the computing complexity using some other measure such as the betweenness. The author assumes the initial load L j of a node j in the power grid is a function of its degree k j and the degrees of its neighbor nodes \({k}_{m}(m \in {\Gamma }_{j})\), where \({\Gamma }_{j}\) is the set of all neighboring nodes of the node j. The initial load of node j is defined as:

$${L}_{j} ={ \left [{k}_{j}\left (\sum\limits_{m\in {\Gamma }_{j}}{k}_{m}\right )\right ]}^{\alpha },$$

and the redistribution between two adjacent nodes is defined as:

$${\Delta }_{ij} = {L}_{i} \frac{{[{k}_{j}(\sum\limits_{m\in {\Gamma }_{j}}{k}_{m})]}^{\alpha }} {\sum\limits_{n\in {\Gamma }_{i}}{[{k}_{n}(\sum\limits_{f\in {\Gamma }_{n}}{k}_{f})]}^{\alpha }}$$

They also set the capacity C j of a node j proportional to its initial load, i.e., \({C}_{j} = T{L}_{j}\), and the cascading process begins when \({L}_{j} + {\Delta }_{ij} > {C}_{j}\). They evaluate the effect of attacking by the normalized avalanche size (broken nodes) \(C{F}_{attack} = \frac{\sum\limits_{i\in A}C{F}_{i}} {{N}_{A}(N-1)}\), where CF i is the avalanche size induced by removing node i. By adjusting the parameter α and T which can influence the initial load and node tolerance, respectively, they numerically studied the electrical power grid of the Western United States with 4941 nodes and 6594 edges to investigate the network robustness under attacks.

Wang and Chen [97] proposed a cascading model with a local weighted flow redistribution rule and studied on weighted scale-free and small-world networks. In their model, they assume the weight (flow) of an edge ij as \({w}_{ij} = {({k}_{i}{k}_{j})}^{\theta }\), where \(\theta \) is the parameter for the strength of the edge weight and k i is the degrees of nodes i. The redistribution model, which is the key to their simulation research, is defined as

$$\Delta {F}_{im} = {F}_{ij} \frac{{w}_{im}} {\sum\limits_{a\in {\Gamma }_{i}}{w}_{ia} +\sum\limits_{b\in {\Gamma }_{j}}{w}_{jb}}$$

where \({\Gamma }_{i}\) is the set of adjacent nodes of i. In the case study, the authors only consider one edge ij attacking and obtain the evaluation result by normalized avalanche size \({S}_{N} = \sum\limits_{ij}{s}_{ij}/{N}_{edge}\), where \({s}_{ij}\) is the avalanche size induced by cutting out edge ij and \({N}_{edge}\) is the total number in the network. They furthermore explore the statistical characteristics of the avalanche size of a network, thus obtaining a power-law avalanche size distribution.

The concept of load entropy, which can be an average measure of a network’s heterogeneity in the load distribution was introduced by Bao, Cao, etc. They consider that a certain degree of instantaneous node overload is permissible in reality complex networks and node brokage is mainly caused by the accumulative effect of overload. They also disagree the simple and unreasonable strategy of immediate removal of an instantaneously overloaded node. By their strategy of the overloaded node removal, it is assumed that the density of the removal probability P(L) of a node obeys uniform distribution in the discrete interval [0, T]. At each time period, the removal probability is calculated as

$${ p}_{i}(t) = \left \{\begin{array}{@{}l@{\quad }l@{}} {p}_{i}(t - 1) + P({L}_{i}(t))/T\quad &\text{ if}\quad {L}_{i}(t) > {C}_{i} \\ 0 \quad &\text{ if}\quad {L}_{i}(t) \leq {C}_{i} \end{array} \right.$$

where \({L}_{i}(t)\) is the load of node i at time t. At each iteration, the load of all nodes is compared with a random \(\beta \in (0,1)\) to determine whether the corresponding node should be removed. When the loads of all nodes are not larger than their corresponding capacity, a cascading failure stops. They define the load entropy to evaluate the robustness of the network under an initial removal on the node with the largest load, but they do not mention about their load redistribution model after certain node’s removal.

In addition, a number of aspects of cascading failures have been discussed in some literatures including the cascade control and defense strategy (Zhao and Gao, 2007 (Cascade defense via navigation in scale-free networks); Sun et al., 2008 (A robust matching model of capacity to defense cascading failure on complex networks); Motter, 2004 (Cascade control and defense in complex networks); Wang and Kim, 2007 (A high-robustness and low-cost model for cascading failures); Ash and Newth, 2007 (Optimizing complex networks for resilience against cascading failure)), the model for describing cascade phenomena (Wang and Xu, 2004 (Cascading failures in coupled map lattices); Wu et al., 2007 (Cascading failures on weighted urban traffic equilibrium networks)), the analytical calculation of capacity parameter (Wang and Rong, 2008 (Effect attack on scale-free networks due to cascading failures); Zhao et al., 2004 (Attack vulnerability of scale-free networks due to cascading breakdown)), and so on.

With the help of modern advanced computers, the simulation of power grid as complex networks has been developed so well that it could help us better understand the dynamics of power network in a way more accurate and less costly in time, therefore it could be applied for blackout analysis and prediction. However, there are some issues associated with that application. First, although there are a lot of proposed measurements for the nodes’ degree or edges’ weight, there is no scientific proof on the validity of these measurements. Second, the values for the tunable parameters in the model are not well recognized, and all those numerical studies are basically experimental. Third, in all the redistribution models, they only consider the conservation of power flow (the modified form of Kirchhoff’s nodal rule), but power grid modeled without applying Kirchhoff’s mesh rule is far away from reality. Fourth, all those models only consider the power transmission. When dealing with power blackout with cascading, at least generators and consumer should be considered into the integrated planning.

Due to those shortcomings above, even numerous recent papers have applied complex network and topology methods with cascading property to study the structure and dynamic function of power grids; results are not so identical and even contrast to each other. Here is a paper from Hines, Cotilla-Sanchez, and Blumsack showing this argument [48]. The authors compare the analysis results from a variety of power networks subjected to random failures and directed attacks with the vulnerability measures of characteristic path length, connectivity loss, and blackout sizes. They chose several contingency methods including random failure, degree attack, maximum/minimum-traffic attack, and betweenness attack. Then conclude that topological measures can provide some general vulnerability indication, but it can also be misleading since individual simulations show only a mild correlation. Most importantly, they suggest that results from physics-based models are more realistic and generally more useful for infrastructure risk assessment.

2.3 Optimization Model

Mathematical optimization methods have been used to solve many power system problems such as planning, operation, and control problems for many years. In order to apply optimization methods for the power problems in reality, some assumptions must be made to derive the mathematical model. However, even under this circumstances, optimization over large-scale power system is still a computation-intensive task within the scope of contemporary information technology. There are so many uncertain factors such as uncontrollable system separation, angle instability, and generation tripping in these large, complex, and widespread power systems that would make the above model more complicated, without considering the new issues introduced by the deregulation of power utilities.

2.3.1 Pre-OPF Model

Before the development of OPF model from its inception in 1961 and several solution methods in existence in 1978, there were some optimization models related to economic power flow dispatch. Megahed et al. [64] propose the conversion of the nonlinearly constrained dispatch problem to a series of constrained linear programming problems. System voltages, active and reactive generation, and the phase angles are considered as prototype part of the OPF problem. These quantities are used in the loss formula. According to the authors, the method is fast and has good convergence characteristics.

2.3.2 OPF Model

Optimal power flow(OPF) model serves as the center and critical part in the mathematical optimization-applied blackout problem over power system. The history of research on OPF model could date back to the early 1960’s [16], and it was derived from the solution of the economic dispatch by the equal incremental cost method.

Economic dispatch is defined as the process of allocating generation levels to the generating units in the mix, so that the system load may be supplied entirely and most economically. Research on optimal dispatch could go as far back as the early 1920s, when engineers were concerned with the problem of economic allocation of generation or the proper division of the load among the generating units available. Generation dispatch has been widely studied and reported by several authors in books on power system analysis [11, 27, 42, 62].

Although both economic dispatch and OPF model are optimization problems with the same minimum cost objective, economic dispatch only considers real power generation and transmission with only power balance equation as the constraint. On the other side, the OPF is a static nonlinear optimization problem which can take nearly all electrical variables, flow balance, power flow physics, generator and demand node bounds, and physical laws in consideration to compute the optimal settings in a power network, given settings of loads and system parameters. A typical OPF model is

$$\begin{array}{rcl} & & \min_{g,s,f,\theta }\quad \sum\limits_{i\in I}({h}_{i}{g}_{i} + {r}_{i}{s}_{i}) \\ & & \sum\limits_{(i,j)\in {\delta }^{+}(i)}{f}_{ij} -\sum\limits_{(j,i)\in {\delta }^{-}(i)}{f}_{ji} = \left \{\begin{array}{ll} {P}_{i} &i \in \mathcal{C} \\ - {D}_{i}&i \in \mathcal{D} \\ 0 &\text{ otherwise} \end{array} \right. \\ & & \sin ({\theta }_{i} - {\theta }_{j}) - {x}_{ij}{f}_{ij} = 0\ \ \forall (i,j) \\ & & \vert {f}_{ij}\vert \leq {u}_{ij}\ \ \forall (i,j) \\ & & {P}_{i}^{min} \leq {P}_{ i} \leq {P}_{i}^{min}\ \ \forall i \in \mathcal{C} \\ & & 0 \leq {D}_{j} \leq {D}_{j}^{nom}\ \ \forall j \in \mathcal{D} \\ \end{array}$$

where a grid is represented by a directed network \(\mathcal{G}\), and:

  • Each node corresponds to a “generator” (i.e., a supply node), or to a “load” (i.e., a demand node), or to a node that neither generates nor consumes power(i.e., a transmission or distribution node). We denote by \(\mathcal{C}\) the set of generator nodes.

  • If node i corresponds to a generator, then there are values \(0 \leq {P}_{i}^{min} \leq {P}_{i}^{max}\). If the generator is operated, then its output must be in the range \([{P}_{i}^{min},{P}_{i}^{max}]\) ; if the generator is not operated, then its output is zero. In general, we expect \({P}_{i}^{min} \geq 0\).

  • If node i corresponds to a demand, then there is a value \({D}_{i}^{nom}\) (the “nominal” demand value at node i). We will denote the set of demands by \(\mathcal{D}\).

  • The arcs of \(\mathcal{G}\) represent power lines. For each arc (i, j), we are given a parameter \({x}_{ij} > 0\) (the resistance) and a parameter \({u}_{ij}\) (the capacity).

Given a set \(\mathcal{C}\) of f operating generators, a power flow is a solution to the system of constraints given above. In this system, for each arc (i, j), we use a variable \({f}_{ij}\) to represent the (power) flow on (i, j) (negative if power is effectively flowing from j to i). In addition, for each node i, we will have a variable \({\theta }_{i}\) (the “phase angle” at i). Finally, if i is a generator node, then we will have a variable P i , while if i represents a demand node, we will have a variable D i . Given a node i, we represent with \({\delta }^{+}(i)\) (\({\delta }^{-}(i)\)) the set of arcs oriented out of (respectively, into) i.

The above constraints is from Ohm’s equation in direct current (DC) network. In the case of an AC network, they can only approximates a complex system of nonlinear equations. The issue of whether to use the more accurate nonlinear formulation, or the approximate DC formulation, is quite not easy. On the one hand, the linearized formulation certainly is an approximation only. On the other hand, a formulation that models AC power flows can prove intractable or may reflect difficulties inherent with the underlying real-life problem.

First, AC power flow models typically include equations of the form:

$$\sin ({\theta }_{i} - {\theta }_{j}) - {x}_{ij}{f}_{ij} = 0\ \ \forall (i,j)$$

Here, the f quantities describe active power flows and the \(\theta \) describe phase angles. In normal operation of a transmission system, one would expect that \({\theta }_{i} \approx {\theta }_{j}\) for any arc (i, j) and thus it can be linearized. Hence the linearization is only valid if we additionally impose that \(\vert {\theta }_{i} - {\theta }_{j}\vert \) be very small. However, in the literature one sometimes sees this “very small” constraint relaxed when the network is not in a normal operative mode. The nonlinear formulation gives rise to extremely complex models, but studies that require multiple power flow computations tend to rely on the linearized formulation to get some useful and straightforward information. Second, no matter we use an AC or DC power flow model, the resulting problems have a far more complex structure than traditional single- or multi-commodity flow models, which would lead to counterintuitive behavior similar to Braess’s paradox.

Originally, classical optimization methods were capable to effectively solve DC OPF, and even AC OPF with certain linear approximation methods. But more recently, due to the wide application of flexible AC transmission system (FACTS) devices and deregulation of power grid, it is difficult to deal effectively with many power system problems through strict old-fashion mathematical formulation. The following paragraphs briefly discuss about the important mathematical optimization techniques used in power systems problems:

  • Linear Programming (LP) and Quadratic Programming (QP) When the objective function, constraints are linear, and decision variables are nonnegative, problems can be formulated as the LP [4, 90]. T.S.Chung et al. [25] proposed a recursive linear programming based approach for minimizing line losses and finding the optimal capacitor allocation in a distribution system. E. Lobato et al. [60] use LP-based OPF to minimize the transmission losses and Generator reactive margins of the Spanish power system. LP can also be used in various power systems applications, including reactive power planning [75] and active and reactive power dispatch [20, 21]. Problems formulated as LP can usually be solved by simplex and interior point (IP) methods, while the scale of problems could be up to thousands of variables and constraints even using inexpensive computers.

    Both the simplex and IP methods can be extended to a quadratic objective function while the constraints maintain linear, which are called QP. J.A. Momoh [67] showed the extension of basic Kuhn-Tucker conditions to employ a generalized quadratic-based model for solving OPF, where the conditions for feasibility, convergence, and optimality are discussed. The same author [69] also published another paper on applying interior point methods to solve quadratic power system optimization problem. N. Grudinin [43] proposed a reactive power optimization model based on successive quadratic programming (SQP) methods, which turned to have the best performance while being compared with other five optimization methods. Nanda [72] developed a new algorithm for OPF using Fletcher’s QP method, and G.P. Granelli et al. [40] proposed security-constrained economic dispatch using dual sequential quadratic programming, which was compared with SQP to demonstrate a better result in computation time and accuracy.

  • Nonlinear Programming (NLP) When the objective function and/or constraints are non linear, problems can be formulated as the NLP. NLP can be applied to various areas of power systems, such as optimal power [68, 91]. J.A. Momoh et al. [105] proposed a nonlinear convex network flow programming (NLCNFP) model and algorithm for solving the security-constrained multi-area economic dispatch problem. D. Pudjianto et al. [81] used NLP-based reactive OPF for distributing reactive power among competing generators in a deregulated market.

    To solve most of the NLP, the most regular way is to start from an initial point and to improve along a certain “descent” direction in which objective function decreases in case of minimization problem, and there are a lot of researches about how to obtain a better initial point and/or “descent” direction associated with its step length ([53, 93]). IP methods originally developed for LP can be applicable here. Sergio Granville [41] presented application of an interior point method to the optimal reactive power dispatch problem. Wei Yan et al. [102] presented the solution of the optimal reactive power flow (ORPF) problem by the predictor corrector primal dual interior point method (PCPDIPM).

  • Integer Programming (IP) and Mixed-Integer Programming (MIP) For some power system related problems (e.g., generator/transmission-line ON status = 1, and generator/transmission-line OFF status = 0), when all or some of the decision variables are can take only integer values, such problem is called integer programming or mixed-integer programming, respectively. They can be applied to many areas of power systems, such as optimal reactive power planning, power systems planning, unit commitment, and generation scheduling [8, 29, 33, 38, 82].

    The most used approaches to solve integer problems using mathematical programming techniques are “branch and bound” and “cutting plane methods” [53, 58]. When the size and complexity of models are large enough, while the structure of the problem is not in specific form (such as transportation network), decomposition technique usually is applied [3, 28].

  • Dynamic Programming (DP) DP based on the principle of optimality states that a sub-policy of an optimal policy must in itself be an optimal sub-policy. DP can be applied to various areas of power systems, such as reactive power control, transmission planning, and unit commitment [49, 78], but it is very inefficient due to the curse of dimensionality.

2.3.3 Unit Commitment

Since power generators cannot instantly turn on to produce power, unit commitment (UC) requirement must be followed in advance so that adequate power generation is always available to meet the demand, especially in the event that generators or transmission lines go out or load demand increases. Unit commitment handles the unit generation schedule in a power system for minimizing operating cost and satisfying prevailing constraints such as load demand over a set of time periods. Unit commitment in power operation planning concerns the scheduling of start-up/shut-down decisions and operation levels for power generation units such that the fuel costs over some time horizon are minimal.

UC is not the same as dispatching. Dispatching focuses on assigning a given set of power plants to another certain set of electric demand, while UC determines the start-up and shutdown schedules of thermal units to meet forecasted demand over certain time periods. The difference between both issues is time. The usual common objectives of unit commitment schedule include minimization of total production cost, minimization of emissions and maximization of reliability and security, and the most important nonlinear constraints are the unit’s minimum up-time and down-time restriction.

Although the planning horizon for unit commitment in principle should be continuous in time, the unit commitment models typically are in discrete time due to the availability of data, the execution time for scheduling decisions, and computation limitation on the complex MIP in continuous time. Here we demonstrate a very basic UC formulation:

$$\begin{array}{rcl} & & \min_{{p}_{i}^{t},{s}_{j}^{t},{w}_{j}^{t}}\quad \sum\limits_{t=1}^{T}\sum\limits_{i=1}^{I}{C}_{ i}({p}_{i}^{t},{u}_{ i}^{t}) +\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{I}{S}_{ i}^{t}({u}_{ i}^{t}) \\ & & {u}_{i}^{t-1} - {u}_{ i}^{t} \leq 1 - {u}_{ i}^{l},\quad i = 1,2,\ldots,I;\quad t = 2,3,\ldots,T - 1 \\ & & l = t + 1,t + 2,\ldots,\min \{t + {\tau }_{i} - 1,T\} \\ & & {l}_{j}^{t} = {l}_{ j}^{t-1} - ({s}_{ j}^{t} - {\eta }_{ j}{w}_{j}^{t}),\quad j = 1,2,\ldots,J \\ & & {l}_{j}^{0} = {l}_{ j}^{in},{l}_{ j}^{T} = {l}_{ j}^{end},\quad t = 1,2,\ldots,T \\ & & \sum\limits_{i=1}^{I}({u}_{ i}^{t}{p}_{ it}^{amx} - p){i}^{t}) \geq {R}^{t},\quad t = 1,2,\ldots,T \\ & & \sum\limits_{i=1}^{I}{p}_{ i}^{t} +\sum\limits_{j=1}^{J}({s}_{ j}^{t} - {w}_{ j}^{t}) \geq {D}^{t},\quad t = 1,2,\ldots,T \\ & & {p}_{it}^{min}{u}_{ i}^{t} \leq {p}_{ i}^{t} \leq {p}_{ it}^{max}{u}_{ i}^{t},\quad i = 1,2,\ldots,I,\quad t = 1,2,\ldots,T \\ & & 0 \leq {s}_{j}^{t} \leq {s}_{ jt}^{max},\quad j = 1,2,\ldots,J,\quad t = 1,2,\ldots,T \\ & & 0 \leq {w}_{j}^{t} \leq {w}_{ jt}^{max},\quad j = 1,2,\ldots,J,\quad t = 1,2,\ldots,T \\ & & 0 \leq {l}_{j}^{t} \leq {s}_{ j}^{max},\quad j = 1,2,\ldots,J,\quad t = 1,2,\ldots,T \\ \end{array}$$

Here, T denotes the number of subintervals of the optimization horizon and suppose there are I thermal as well as J pumped-storage hydro units. The variable \({u}_{i}^{t} \in \{ 0,1\},\quad i = 1,2,\ldots,I,\quad t = 1,2,\ldots,T\) indicates whether the thermal unit i is in operation at time t. Variables \({p}_{j}^{t},{s}_{j}^{t},{w}_{j}^{t},\quad j = 1,2,\ldots,J,\quad t = 1,2,\ldots,T\) are the output levels for the thermal units, the hydro units in generation and in pumping modes, respectively. The variables l j t denote the fill (in energy) of the upper dam of the hydro unit j at the end of interval \(t,\quad j = 1,2,\ldots,J,\quad t = 1,2,\ldots,T\). The objective is the sum of the fuel cost and start-up cost with parameter \({C}_{i},{S}_{i}^{t}\), respectively, and the constraints include the power output bounds of units and the fill of the upper dam, load coverage, reserve management of the thermal units, balances for the pumped-storage plants, and minimum down times for thermal stresses in the coal fired blocks.

The most straightforward way to solve the UC economic optimization is brute force, which enumerates all possible combinations, eliminates the possibilities that do not meet the obligations set, and finally chooses the best of all the remaining possibilities. Even though this algorithm is computationally intensive, most of current methodologies are a variation on the brute force, in which some procedures are added to reduce the number of possibilities enumerated.

The unit commitment problem belongs to the class of complex combinational optimization problems. Several mathematical programming techniques have been proposed to solve this time-dependent problem.

  • Dynamic Programming (DP) DP searches the solution space that consists of the units’ status for an optimal solution [89]. The search can be carried out in a forward or backward direction. The time periods of the study horizon are known as the stages of the problem. The combinations of units within a time period are known as the states ([44, 51]). Lowery [49] starts from a previously determined optimal UC planning and gradually adds power plants to obtain optimal solutions for higher demands. Hobbs et al. [61] initialize their approach with options calculated for preceding periods. Cohen and Yoshimura [26] proposed a branch-and-bound model which starts from a previously obtained optimum. The UC problem may also be decomposed into smaller subproblems that are easily managed and solved with DP, where the master problem is optimized, linking the subproblems by Lagrange multipliers. Van den Bosch and Honderd [15] decomposed the main problem into several sub-problems that are easier to solve. The decomposition proposed by Snyder et al. [89] consists of grouping power plants from the same type.

    The advantage of DP is its ability to maintain solution feasibility. DP builds and evaluates the complete “decision tree” to optimize the problem at hand. But it suffers from the “curse of dimensionality” because the problem size (number of states) increases rapidly with the number of generating units to be committed, which results in an unacceptable solution time. To reduce the dimension, search space, and execution time, several approaches have been developed, including DP-SC (dynamic programming-sequential combination) [77], DP-TC (dynamic programming-truncated combination) [76], DP-STC (which is a combination of the DP-SC and DP-TC approaches) [57], and DP-VW (variable window-truncated dynamic programming) [76]. The variation of window size according to load demand increment indicates a substantial saving in computation time without sacrificing the quality of the solution, and the solution of all of these DP methods is sub-optimal.

  • Dynamic and Linear Programming The UC problem can be solved by using regular dynamic programming (DP) or DP with successive approximation of the solution space. Linear programming (LP) solves the economic dispatch within UC for optimal allocation of fuel/generation. Dantzig-Wolfe decomposition, when used, partitions the linear program into smaller, easily manageable LP subproblems [37, 95]. The primary disadvantage of LP solutions is the numerous variables needed to represent the piece-wise linear input-output curves.

2.3.4 Contingency and Interdiction

Contingency and interdiction analysis, which assesses the ability of the power grid to sustain various combinations of power grid component failures based on state estimates, is a critical part of the energy management system. Here, the contingency means a set of unexpected events happening within a short duration. The unexpected events can be failures of buses (generators, substations, etc.) or transmission and distribution lines. Optimization is used to maximize the blackout size due to contingencies caused by attack with limited resources [9, 32, 86].

In the past, due to the heavy computation involved, the contingency analysis can be only analyzed for only a select set of N − 1 contingency, or N − 1 reliability case, where the failure of one component (a bus or a line) has been an active research area. Milano et al. uses N − 1 contingency criterion as an initial optimal operating condition to estimate the system-wide available transfer capability [66]. Hedman et al. analyze the N − 1 reliable DC optimal dispatch with transmission switching by modifying economic dispatch optimization problems to incorporate the flexibility of transmission assets’ states [47]. While ensuring N − 1 reliability, the same authors also present a co-optimization formulation of transmission switching problem and the generation unit commitment [46].

However, as electricity demand continues to grow and renewable energy increases its penetration in the power grid, analysis of the N − 1 reliability is not sufficient for many real applications with multiple failures to discover the vulnerabilities of power grids. Although the combinatorial number of contingency states imposes a substantial computational burden for analysis, the N − k contingency analysis for failures of multiple components (totally k buses and lines) can reflect a larger variation of vulnerabilities of a power system and attract a lot of research focus. Salmeron, Wood, and Baldick applied a linearized power flow model and used a bi-level optimization framework along with mixed-integer programming to analyze the security of the electric grid and to obtain the worst contingency selection, where the interdiction model is to “identify critical sets of a power grid’s components, for example generators, transmission lines, and transformers, by identifying maximally disruptive, coordinated attacks on a grid, which a terrorist group might undertake”[86]. Pinar et al. modeled the power grid vulnerability analysis as a mixed-integer nonlinear programming (MINLP) problem and used a special structure in the formulation to avoid nonlinearity and approximate the original problem as a pure combinatorial problem [80]. Bienstock used the two approaches of the integer programming and a new, continuous nonlinear programming formulation for comparison on vulnerability evaluation over large-scale power grid failures [1, 13, 14].

In the paper from Fan et al. [36], the critical node method, originally used for research in general graphs [10], is in the first time to be applied to study on power grids, which is one of the main contribution of this paper. More importantly, this paper is among of the first few papers to evaluate different N − k contingency selection by graph algorithms and interdiction methods through the economic objective (generating and load shedding cost) of those contingency states. In this paper, several graph algorithms and interdiction methods for contingency selection are surveyed and compared with our new method represented in formulation. Their new model can select the contingency state including both buses and lines, which is a big plus than the others. Also the evaluation measurement on economical emphasis is quite new, and lead to some interesting conclusions.

2.4 Blackout with Distributed Generation

Traditionally, electricity industries generate most of their power in large and centralized facilities, such as fossil fuel, nuclear, large solar or hydropower sources. This kind of business strategies has excellent economies of scale and some other considerations, such as of health and safety, logistics, environment, geography, and geology, but usually electricity transmission over long distances would negatively affect the environment. The other approach is via distributed generation, which can reduce the amount of energy lost in transmission and the size of transmission infrastructure due to closeness between supply and demand. A very good application example of distributed generation is microgrid, which is a localized grouping of electricity generation, energy storage, and loads. Under normal operating condition, it is connected to a traditional centralized grid; however, it could be disconnected from there functioning autonomously. From the point of view of the electricity network operator, a microgrid could be treated as one entity, but instead of simply receiving electricity supply, it could sustain itself for a long time without external electricity source or even sometimes output electricity for others.

The blackout is always preceded by a sequence of cascading failures which breaks down transmission lines and generators, and thus leads to large variation in power flow, its routing, and bus voltage due the mechanism of load balance in a massively interconnected network system. With the emerging of distributed generation, the phenomena of islanding must be taken in consideration during blackout analysis, especially for real-time decision making in the early stage of possible blackout. Islanding is the situation where a distributed generator continues to power a neighborhood while electrical grid power from the electric utility is not available.

By proper management of intentional islanding, the operator disconnects those “islands (localized grouping of electricity generation, energy storage, and loads)” from the grid and forces the distributed generator to supply power for the local demand. Strategy like this could largely reduce the burden of substations and generators which are already crumbling due to emergent power rerouting to meet the remote power demand during power outage and relieve the overloading transmission lines during the critical restoration phase [71]. Distributed generation could increase the reliability and security of power supply [6] by providing electricity to the medium-voltage and low-voltage networks where it is most needed, in case of higher-voltage network failures. A lot of conceptual but pioneer papers have been published on how to apply islanding operation to mitigate the spread of power outage and prevent possible blackout [31, 35, 59, 87] however, due to the complexity of interacting mechanism within the “island” and “interislands,” there are quite a few preliminary researches on real-time algorithm to quickly detect the possible optimal islanding strategy when power system vulnerability is approaching to an extreme emergency state [70, 79, 103, 104].