Review on Energy Resilience

Contents lists available at ScienceDirect

Reliability Engineering and System Safety

journal homepage: www.elsevier.com/locate/ress

Optimizing power system investments and resilience against attacks

Yiping Fang, Giovanni Sansavini ⁎

Reliability and Risk Engineering Laboratory, Institute of Energy Technology, Department of Mechanical and Process Engineering, ETH Zurich, Leonhardstrasse 21, 8092 Zurich, Switzerland

A R T I C L E I N F O

Keywords: Electric power network protection System resilience Transmission switching Attacks Trilevel optimization

A B S T R A C T

This paper studies the combination of capacity expansion and switch installation in electric systems that ensures optimum performance under nominal operations and attacks. The planner–attacker–defender model is adopted to develop decisions that minimize investment and operating costs, and functionality loss after attacks. The model bridges long-term system planning for transmission expansion and short-term switching operations in reaction to attacks. The mixed-integer optimization is solved by decomposition via two-layer cutting plane algorithm. Numerical results on an IEEE system shows that small investments in transmission line switching enhance resilience by responding to disruptions via system reconfiguration. Sensitivity analyses show that transmission planning under the assumption of small-scale attacks provides the most robust strategy, i.e. the minimum-regret planning, if many constraints and limited investment budget affect the planning. On the other hand, the assumption of large-scale attacks provides the most robust strategy if the planning process involves large flexibility and budget.

1. Introduction

Electrical transmission networks (ETNs) are critical infrastructures (CIs) [1,2]. Modern societies critically depend on their seamless operation for transmitting electric energy usually from remote genera- tion plants to densely populated areas. Motivated by sustainability concerns, many governments enforce regulations that increase the fraction of energy generation from renewable energy sources (RES). For example, the Swiss Federal Council has developed a long-term energy policy (“Energy Strategy 2050”) to gradually phase out nuclear energy, which amounts to around 39% of the country electric genera- tion, and substitute it mainly by RES such as hydro, solar and wind power [3]. Germany has also increased the RES generation in the electricity sector from 6.3% in 2000 to about 30% in 2014 [4] and the RES share is expected to reach 80% by 2050 [5]. However, infra- structure investments needed to accommodate a massive share of RES into the system usually lag behind, e.g. Germany lacks the infrastruc- ture to transport the power generated from the North Sea offshore wind farms to southern regions. As a result, power is looped through neighboring Countries (Poland and the Czech Republic), thereby causing unnecessary power flows and congestion, and increasing the threat of power blackouts. Furthermore, ETN operators are challenged by increasing energy demand and grid congestion [6]. Therefore, transmission expansion (TE) by increasing capacity via building new or doubling existing transmission lines is instrumental in coping with

changes in power flow patterns. Transmission expansion planning (TEP) denotes the decision-

making process faced by system planners when reinforcing ETNs, i.e., selecting the capacity and location of new transmission assets to be installed in the power systems in order to ensure their feasible, reliable, and economic operation [7]. TEP has been extensively studied follow- ing the pioneering work by Garver [8]. Classical TEP minimizes investment and operation costs and assumes deterministic power generation and demand forecasts over the planning horizon. The problem is traditionally addressed with an optimization formulation, e.g. linear programming [9,10], mixed-integer linear formulation [11– 13], dynamic programming [14], non-convex optimization technique [15], and decomposition methods [16]. Extensive reviews on these models can be found in Latorre et al. [17] and Romero et al. [18].

TEP usually involves a planning horizon of several years, e.g. 10 years [19]. Thus, the decisions on TEP are made under great uncertainty, e.g. stemming from future electric demand levels and the fluctuating power output of RES. The uncertainty aspects within the TEP problem have been increasingly addressed in recent years. Diverse uncertainty sources, e.g. component reliability uncertainty [20] and electricity market uncertainty [21,22], have been considered. TEP under uncertainty is mainly formulated in two frameworks: stochastic optimization [23] and robust optimization [24,25], where the former requires an accurate specification of the probability distribution of the uncertain parameters, while the later only requires knowing the range

http://dx.doi.org/10.1016/j.ress.2016.10.028 Received 27 April 2016; Received in revised form 14 September 2016; Accepted 30 October 2016

⁎ Corresponding author. E-mail address: [email protected] (G. Sansavini).

Reliability Engineering and System Safety 159 (2017) 161–173

Available online 05 November 2016 0951-8320/ © 2016 Elsevier Ltd. All rights reserved.

MARK

of variation of the uncertain parameters. Most recent reviews of TEP under uncertainty can be found in Sorokin et al. [26] and Hemmati et al. [27].

Despite the large amount of studies on TEP under uncertainties, very few studies have considered uncertainty due to system disrup- tions. Designing an ETN robust against failure events, i.e. contingen- cies, is critical to ensure reliable power supply. In this respect, TEP should also be driven by security and vulnerability concerns in the new context where malevolent destructive agents come into play. Actually, the threat of terrorist attacks on the power transmission system has become increasingly prominent in recent years. Around 2500 attacks have been conducted against transmission lines and towers in the past decade, and the electric power system is considered to be an attractive target by terrorists [28]. The US Committee on Science and Technology for Countering Terrorism recommends that “The nation's electric power systems must clearly be made more resilient to terrorist attack” [29], where resilience means system has the ability to prepare and plan for, absorb, recover from, and more successfully adapt to adverse events [2,30,31]. It is advocated that we ought to accept the reality that our CIs, including the electrical power systems, are threatened by terrorism, and terrorism risk management measures such as hardening and adding surety to CIs by adding redundancy, robustness and resiliency, need to be investigated [32–36].

TEP under potential deliberate attacks has been particularly studied by Carrión, Alguacil and Arroyo [37–39]. The uncertainty associated with malevolent outages is modelled through scenarios which are generated based on the solution of the so-called “terrorist threat problem” [40]. In Carrión et al. [37], stochastic optimization is used and the results show that additional investments in TE alleviate the severe consequences of deliberate attacks. However, probability-based risk assessment ap- proaches are deficient and unjustified for terrorism risk analysis [41], mainly because that attack probabilities maybe impossible to estimate accurately and that probabilities estimated based only on what we know, rather than on what the attacker might know, can lead to poor risk management decisions [42]. Instead, Brown and Cox [42,43] suggest the use of robust decision analysis with the instrumental rationality assump- tion, meaning that the actors are assumed to choose actions that maximize their subjective expected utility [44]. The application of the minimax weighted regret paradigm [39] shows that robust optimization is a more appropriate framework to model low likelihood but potentially cata- strophic events such as deliberate outages.

In addition to investments in augmenting transmission capacity, system operators need developing feasible actions in response to disruptive events that ensure satisfying customers demand and prevent system-wide instabilities, i.e. towards system self-healing [45,46]. The traditional response to disruptions involves changing the power flows on transmission lines by varying the generator dispatch. In recent years, a variety of active network control technologies, including FACTS devices, tap changing transformers, phase shifters and trans- mission switching, have emerged and can provide response actions to alleviate the effects of contingencies in ETN [47]. Transmission switching (TS), i.e. the practice of changing system topology by opening (or closing) a circuit breaker on appropriately-selected transmission lines, is recognized as a relatively inexpensive corrective mechanism to enhance system security and to reduce line overloads, voltage pro- blems, and power losses [48]. Topological modifications are usually employed in distribution networks and exploit the radial and loop structure in order to restore supply to de-energized loads in isolated out-of-service regions [49]. However, TS can also be utilized in transmission networks to effectively reduce the amount of load shed following critical N − 1 and N − 2 line and generator contingencies [50]. TS can improve system resilience [51] and reliability by applying post-contingency corrections [52]. Moreover, TS can serve as a proactive measure for economically operating the system. Fisher et al. [53] studied the co-optimization of generation dispatch and proactive TS and showed that TS reduced operating costs substantially.

Villumsen et al. [23,54] analyzed the impact of TS on the optimal expansion of transmission network under future uncertainty in de- mand and wind generation capacity and found that TS increases the utilization of transmission networks and wind power penetration.

In this study, we consider investments in both TE and TS as strategic tools that ensure ETNs efficiency in normal conditions and resilience after deliberate attacks. The problem is formulated as decision-making on new transmission lines to be built from a candidate set, and on advanced line switching devices to be installed which adjust the system topology in reaction to disruptions. Although circuit breakers are the common component in ETNs, their automation requires investments in communication equipment. The investments are quantified by the costs of building candidate lines and of installing switching devices and are constrained by the investment budget. The objective of the decision-making is to attain an ETN with a minimum investment that operates efficiently in nominal conditions, and max- imizes system resilience against deliberate outages, where resilience is provided in the medium term by adaptive transmission switching and power re-dispatching after outages. The uncertainty associated with deliberate outages is modelled by an intelligent agent who maximizes the system damage by attacking a set of components, subject to limited disruptive resources. The attacker has perfect knowledge of the system and can inflict the maximum damage. After the attack, the system operator minimizes the system damage, by means of TS and power flow re-dispatching towards undamaged transmission facilities. The pro- posed optimization problem is modelled within a three-level planner- attacker-defender framework, similar to the defender-attacker inter- actions game (sometimes called as leader-follower game [55]) models that were used for the defense planning of power grids [56–58], CI systems [59–61], or more general multi-state complex systems [62]. Hausken and Levitin have provided a thorough review on this topic [63]. The mathematical formulation of the model has a min-max-min multilevel structure, which is strongly NP-hard [64]. Adding to the computational complexity, the short-term TS applied in response to disruptions renders the right-hand side minimization a mixed integer programming (MIP) problem. Benders decomposition and its exten- sions [60,65] might become inapplicable because the strong duality does not hold in general MIP problems. In this study, a recent constraint-and-column strategy which creates cutting planes based on primal decision variables [66] is extended, as in Zeng and An [67], and provides an efficient solution algorithm.

The paper has three main contributions: (i) the planner-attack- defender model which translates into a three-level MIP problem is proposed to efficiently address transmission expansion and switch installation, that bridges the long-term planning time-scale and the short-term operational time-scale in electric power systems; (ii) an efficient decomposition solution algorithm is developed that allows tradeoffs between resilience and economic objectives, and the para- meterization of optimal solutions with respect to the investment budget and credible attack budget; (iii) the application to a realistic case study illustrates integrated investment plans which combine system expan- sion and reconfiguration capability to enhance system resilience.

The remainder of the paper is organized as follows. Section 2 proposes a detailed formulation of the trilevel planner-attacker-defen- der model for the optimal investment planning of ETNs under intentional attacks considering both line capacity expansion and installation of switches. The methodology adopted for the solution of the proposed model is introduced in Section 3. Section 4 presents the analysis of the computational results obtained from the application to the IEEE 14-bus test system. Concluding remarks are discussed in Section 5.

2. The planner–attacker–defender model

The proposed three-level planner-attacker-defender model repre- sents (i) network planners who make investment decisions pursuing

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

162

minimum total cost, (ii) attackers who maximize system disruptions subject to an attack budget, and (iii) the implementation of short-term operation decisions aiming at minimum system performance loss after the attack. The model includes the following novel features: (i) network planners invest in TE and TS simultaneously in the planning phase; (ii) the objective combines the minimization of the weighted sum of the total nominal costs (i.e. investment costs and operating costs without deliberate outages) and of the largest possible system performance loss under potential intentional attacks; (iii) system operators respond by enacting power re-dispatching and TS simultaneously for the mitiga- tion of system performance drop. Note that system damages caused by an attack remain after short-term re-dispatching and TS operations.

The optimal investment planning of ETNs is framed within the three-level min-max-min formulation which implements the planner- attacker-defender model. The ETN is represented as a set of nodes (buses) N , connected by a set of arcs (transmission lines) L. The model assumes that:

(i) linear DC power flow characterizes the behavior of the transmis- sion network; this model is a commonly adopted simplification in ETN planning [17,68];

(ii) the most common components disrupted by destructive agents are transmission lines [28]; thus, this study focuses on deliberate outages of these assets, and the approach can be extended to account for the outages of other components;

(iii) during nominal operating condition, a single load scenario is modelled, i.e. the expected load demand forecast over the plan- ning horizon;

(iv) interdiction from the attacker is complete, i.e., the components are completely unusable after the attack;

(v) the system operators are aware of the status of all the components after the occurrence of outage, e.g., through information and communication technology (ICT) applications [69].

The three-level model uses the following notation:

Indices, sets and parameters n Index used for network buses (nodes) l Index used for transmission lines N Set of buses NG Set of generators ND Set of demand nodes L Set of transmission lines in the original trans-

mission network

LC Set of candidate lines Bl Inverse of the reactance of line l F l( ) Origin or sending node of line l T l( ) Destination or receiving node of line l Pn

G Capacity of generator n

Pl L Capacity of line l

Pn D Total demand at node n

Πmax Investment budget

Amax Attack budget K Maximum number of lines allowed to be switch-

able

cl b Cost of building candidate line l

cl s Switch installation cost at line l

cn G Cost of power generation at node n N∈ G

cn LS Load shedding cost at node n N∈ D

σ Weighting factor for the operating cost under nominal conditions

α Weighting factor for the cost of deliberate outages Decision variables

bl Binary variable that is equal to 1 if candidate line l is built, being 0 otherwise

sl Binary variable that is equal to 1 if a switch is installed at line l, being 0 otherwise

xl Binary variable that is equal to 1 if line l is swit- ched in, being 0 otherwise

vl Binary variable that is equal to 0 if line l is de- stroyed by an attacker, being 1 otherwise

θn Phase angle in node n fl Power flow in line l Pgn Power output at generator node n N∈ G LSn Load shedding in node n N∈ D var 0 Variables under nominal operating conditions

without deliberate attacks (represented by the superscript 0), where var includes binary variables xl and continuous variables θ f P, ,n l gn and LSn

Problems notations b sAP( , )l l Attack problem: it models the attack of the dis-

ruptive agent after the realization of the planning investment decisions bl and sl, and returns the maximum value of the minimal possible load shedding achieved by corrective operations after the attack

b s vDRP( , , )l l l Defender response problem: it models the system operators’ corrective actions after an attack, and returns the minimum system load shedding that is achieved through TS and power flow re-dispatch- ing

The mathematical formulation of the planner-attacker-defender model for the optimal investment planning of ETNs is:

Level 1

∑ ∑c b c sSubject to: + ≤Π l L

l b

l l L L

l s

l max

∈ ∈ ∪H C (1b)

∑ s K≤ l L L

l ∈ ⋃ C (1c)

f B θ θ s s x l L= ( − ) (1 − + ) ∀ ∈l l F l T l l l l 0

( ) 0

( ) 0 0

(1d)

f B θ θ s s x b l L= ( − ) (1 − + ) ∀ ∈l l F l T l l l l l C0

( ) 0

( ) 0 0

(1e)

(1a).

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

163

∑ ∑ ∪ ∪

P f f LS P n N− + + = ∀ ∈gn l L L F l n

l l L L T l n

l n n D0

( ∈ , ( )= )

0

( ∈ , ( )= )

0 0

C C

(1f)

P f P l L L− ≤ ≤ ∀ ∈ ⋃l L

l l L C0

(1g)

P P n N0≤ ≤ ∀ ∈gn n G

G 0

(1h)

LS P n N0≤ ≤ ∀ ∈n n D

D 0 (1i)

b l L={0, 1} ∀ ∈l C (1j)

s l L L={0, 1} ∀ ∈ ⋃l C (1k)

x l L L={0, 1} ∀ ∈ ⋃l C 0

(1l)

Level 2. Where

(2a).

∑ v ASubject to : (1 − )≤ l L L

l max

∈ ∪ H (2b)

v l L L={0, 1} ∀ ∈ ⋃l C (2c)

Level 3. Where

(3a).

f B θ θ s s x v l LSubject to : = ( − ) (1 − + ) ∀ ∈l l F l T l l l l l( ) ( ) (3b)

f B θ θ s s x b v l L= ( − ) (1 − + ) ∀ ∈l l F l T l l l l l l C

( ) ( ) (3c)

∑ ∑ ∪ ∪

P f f LS P n N− + + = , ∀ ∈gn l L L F l n

l l L L T l n

l n n D

( ∈ , ( )= ) ( ∈ , ( )= )C C

(3d)

P f P l L L− ≤ ≤ ∀ ∈ ⋃l L

l l L C (3e)

P P n N0≤ ≤ ∀ ∈gn n G

G (3f)

LS P n N0≤ ≤ ∀ ∈n n D

D (3g)

x l L L={0, 1} ∀ ∈ ⋃l C (3h)

The optimization problem (1)–(3) comprises three levels: (i) the first level (1a)-(1l) models the decisions of the system planners; (ii) the second level (2a)-(2c) characterizes the behavior of the disruptive agent following the realization of planning investments, and is called attack problem (AP); and (iii) the third level (3a)-(3h) models the system operators’ corrective actions by TS and power flow re-dispatching after the attack, and is called defender response problem (DRP).

2.1. First level − Planner's problem

In the design phase, the system planners perform investment decisions for adding switching capability and transmission capacity to an ETN with the objective of minimizing the total system costs and the maximum performance loss after attacks over the planning horizon (1a). Therefore, the planner's objective includes two terms, (i) the investment costs, i.e. new lines and switches at unit costs cl

b and cl s,

respectively, and operating costs in nominal conditions, i.e. generation costs and loss-of-supply costs to enforce power balance with unit costs cn

G and cn LS, respectively (operating costs are discounted by a factor σ to

make them comparable to investment costs); and (ii) the system performance loss after attack, which is given by the solution of the

level-two optimization, i.e. b sAP( , )l l , presented in Section 2.2. The weight α models the planner's propensity towards resilience or economic issues. In this model, resilience is measured by the costu- mer's demand that cannot be supplied due to the system topology after the attack, b sAP( , )l l , and it results from the interplay between the attack damages and the defender's response by topology changes. This resilience metric integrates both the impact of shocks and the system recovery capability [2,61,70]. The investment decisions are represented by binary variables bl and sl, b =1l if the candidate transmission line l L∈ C is built and b =0l otherwise, s =1l if a switch is installed on line l L L∈ ⋃ C and s =0l otherwise. The investment budget constraint Πmax is given in (1b). Following previous studies of optimal TS [47,53,54], the number of transmission lines that can be switchable is limited by constraint (1c) to reduce the complexity of system operations. This also reduces the computational complexity. Given the investment decisions bl and sl, the system operators choose suitable switching operations xl

0, and flow dispatching decisions P f θ, ,ng l n

0 0 0 with the objective of mini-

mizing the total operating cost. The binary variables x =1l 0 if line l is

switched on and x =0l 0 otherwise. The constraints (1d)–(1i) represent

the physical operations of the network. Kirchhoff's laws are incorpo- rated in (1d) and (1e) for original transmission lines and candidate lines, respectively. The term s s x(1 − + )l l l

0 in (1d) models the operation statuses of the transmission lines in the original network, ensuring that the switching of line l is only possible if a switch is installed (s =1l ). Likewise, the term s s x b(1 − + )l l l l

0 in (1e) allows the switching of line l only if the line l exists (b =1l ) and it is equipped with a switch (s =1l ). Power balance at each node is enforced by (1f), and (1g) limits the power flow across line l to its capacity. Constraint (1h) bounds the output of generator at node n by its capacity, and (1i) ensures that the total load shedding at node n in non-negative and smaller than the total load demand at that node. (1j)–(1l) are standard integrality con- straints.

2.2. Second level − Attacker's problem

The attacker's choice of the components to target is captured by the second-level attack problem b sAP( , )l l , which is parameterized in terms of the first-level variables bl and sl. The decision is modelled by the binary variables v =0l if the line l is targeted, and v =1l otherwise. The attacker aims to maximize the system disruption quantified by the load shedding after the attack (2a), which is determined in the third level defenders’ response problem b s vDRP( , , )l l l , presented in Section 2.3. The attack budget is modelled through a simple knapsack constraint (2b) by setting the maximum number of transmission lines that can be targeted. (2c) is the integrality constraint.

2.3. Third level − Defender's response problem

The system operator's response to the attack is modelled by the b s vDRP( , , )l l l optimization in (3a)–(3h). The power re-dispatch and TS

in the third phase depend on the attacker's decisions in the second- phase and on the planning decisions in the first-phase. As a result,

b s vDRP( , , )l l l is conditioned on the first-level variables bl and sl, and on the second-level variables vl. The system operators’ objective (3a) is to minimize the load shedding LSn caused by the consequences of the attack via combined transmission switching (xl) and power flow re- dispatching (P f θ, ,gn l n) towards operating transmission lines. Load shedding aims at satisfying operational constraints and physical limits. Similar to the constraints (1d)–(1i) in nominal conditions, (3b)–(3h) model operations by DC power flow and physical limits after the attack. In level three, the status of transmission lines represented by the terms

s s x v(1 − + )l l l l in (3b) and s s x b v(1 − + )l l l l l in (3c) embed the attack variables vl, i.e. line switching is possible only if line l is not destroyed (v =1l ) and it is equipped with a switch (s =1l ). By the same token, the switching of new lines (b =1l ) is only possible if they are not destroyed (v =1l ) and a switch has also been installed (s =1l ).

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

164

3. Solution methodology of the mixed-integer nonlinear trilevel programming problem

The min-max-min formulation (1)–(3) of Section 2 configures a mixed-integer nonlinear trilevel programming problem. The main challenges for its solutions are associated with (i) the nonlinear combinations of binary and continuous variables in (1d)–(1e) and (3b)–(3c); (ii) binary variables in the second level which prevent the equivalent single-level representation of the whole problem [59]; (iii) binary variables in the third level which prevent the merging of the two inner problems, i.e. the second and third level max-min problems, into a single max problem using the Karush-Kuhn-Tucker (KKT) conditions (or the strong duality) of the third level min problem. Therefore, solution methods that depend on the gradual reconstruction of the upper stage problem using dual information from the lower stage [57,60,65,71] are inapplicable.

In this paper, we adopt a cutting plane strategy which is based on primal cuts [66], involving only primal decision variables, i.e. invest- ment, attack and operational variables, and we extend it to solve the three-level planner-attacker-defender problem (1)–(3). As illustrated in Fig. 1, the problem is decomposed into an outer-layer master problem (15) and an outer-layer subproblem (7), which iteratively exchange primal investment variables b s,l l and attack decision vari- ables vl until convergence to an optimal solution. The solution of the outer-layer master problem (15) provides (tentative) investment decisions b s,l l, and the solution of the outer-layer subproblem (7) provides the attacker's optimum plan vl, i.e. the worst attack from the system planner's perspective. The latter can be expanded into a max- min-min formulation by separating continuous and binary variables. The outer-layer subproblem (7) is solved (i) by decomposing it into an inner-layer master problem (12) and an inner-layer subproblem (13), and (ii) by applying a cutting plane method which iteratively exchange

primal attack variables vl and switching decision variables xl until convergence to an optimal solution [66]. Therefore, the proposed algorithm to solve the problem (1)–(3) has a two-layer master- subproblem structure; in each layer a cutting plane strategy is applied, usually referred to as constraint-and-column generation method [25,66].

In Section 3.1, we develop a compact abstract formulation for the problem (1)–(3) in order to facilitate its algorithmic solution, and the solution technique is detailed in Sections 3.2–3.3.

3.1. Compact formulation

In order to facilitate the development of the solution algorithm, the original nonlinear problem (1)–(3) is replaced by its compact linear formulation. The nonlinearity in (1)–(3) stems from the combination of discrete and continuous variables in constraints (1d)–(1e) and (3b)– (3c). However, since all the discrete variables are binary, constraints (1d)–(1e) and (3b)–(3c) can be linearized exactly because they contain products of binary and continuous variables.

After substituting θ θ−F l T l( ) 0

( ) 0 with θΔ 0and defining additional binary

variables z s x=l l l 1 0 and z s s x b=(1 − + )l l l l l

2 0 , constraints (1d)–(1e) can be replaced by:

f B s z θ l L= (1 − + ) Δ ∀ ∈l l l l 0 1 0

(4a)

f B z θ l L= Δ ∀ ∈l l l C0 2 0

(4b)

z z s z x z s x l L∈ {0, 1}: ≤ , ≤ , ≥ + −1 ∀ ∈l l l l l l l l 1 1 1 0 1 0

(4c)

z z b z s z z b s z l L∈ {0, 1}: ≤ , ≤1 − + , ≥ − + ∀ ∈l l l l l l l l l l C2 2 2 1 2 1

(4d)

Furthermore, constraints (4a)-(4b) can be linearized using the “Big- M” construction [72] and replaced by:

M s z f B θ M s z l L− [1 − (1 − + ) ]≤ − Δ ≤ [1 − (1 − + ) ] ∀ ∈l l l l l l 1 0 0 1

(5a)

M z f B θ M z l L− (1− )≤ − Δ ≤ (1− ) ∀ ∈l l l l C2 0 0 2

(5b)

and after this change, constraint (1g) is replaced by:

P s z f P s z l L− (1 − + )≤ ≤ (1 − + ) ∀ ∈l L

l l l l L

l l 1 0 1

(5c)

P z f P z l L− ≤ ≤ ∀ ∈l L

l l l L

l C2 0 2

(5d)

Constraints (3b)–(3c) can be linearized following the same techni- que.

After linearization, the planner-attacker-defender model (1)–(3) can be written in an abstract form:

δ by cyamin + +max min δ x y v x y δ v, ,

0 ∈Λ , ∈Φ ( , )0 0 (6a)

δ Ex Fy gDSubject to : + + ≤0 0 1 (6b)

δ x y( , , )∈{0, 1} ×{0, 1} ×m m m0 0 +1 2 3 (6c)

v Hv gΛ = { ∈{0, 1} : ≤ }m 24 (6d)

δ v x y Rx Wy g δ QvPΦ ( , )={( , )∈{0, 1} × : + ≤ − − }m m+ 32 3 (6e)

where constraints (6b)-(6c) correspond to constraints (1b)-(1l); con- straint (6d) corresponds to constraints (2b)-(2c); constraint (6e) corresponds to constraints (3b)–(3h), and bold lower-case letters refer to vectors, and bold upper-case letters refer to matrices. δ represents the binary investment variables bl and sl, x0 represents the binary operation variables xl

0, and y0 represents the continuous operation variables P f θ LS, , ,ng l n n

0 0 0 0 in the first stage problem. Λ indicates the finite and countable set of possible attacks. δ vΦ ( , ) indicates the feasible operating actions of the system operators in the third level response problem after planning decisions are made and the attack is performed, where x and y are the binary and continuous operating variables, respectively. Matrices D E, , F H R W P Q, , , , , contain the

Fig. 1. Flow diagram of the two-layer constraint-and-column generation algorithm. Optimality (Opt.) gap refers to the relative difference between the upper and lower bound of the objective evaluated by solving the master problem and the subproblem, respectively, as discussed in Table 1, 2.

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

165

coefficients of variables in the constraints and vectors g g g, ,1 2 3 contain the right-hand side parameters in the constraints. m m m m, , ,1 2 3 4 are the dimensions of the vector spaces of variables δ x, and x y,0 and y v,0 , respectively, and vectors a b c, , represent coefficients of variables in the objective function (1a).

3.2. Outer-layer subproblem and its solution by the inner-layer algorithm

The subproblem associated with the planner-attacker-defender problem (6) is

δ cy( *)=max min v x y δ v∈Λ , ∈Φ ( *, ) (7)

where δ* represents a realization of the first stage investment decision. The max-min bilevel problem (7) has both binary variables x and

continuous variables y. By observing that for any given fixed invest- ment plan δ* and attack plan v, the δ vDRP( *, ) is feasible (e.g. a permanent feasible solution is simply x=0 and y=0, i.e. shedding all the load), we let any feasible x define a feasible switching plan (FSP). All the FSPs constitute a countable and bounded set δ vΦ ( *, )x , which can be enumerated as δ v x |i I}Φ ( *, )={ = 1…ix where I is the cardinality of δ vΦ ( *, )x . For any FSP xi, the set

δ v x y Wy g Pδ Qv RxΦ ( *, , )={ ∈ : ≤ − *− − }i iy m+ 33 ensures the feasibility of the operating decision variables y for each δ v*, and xi. Therefore, we can separate the binary variables x and the continuous variables y in the formulation of the subproblem (7):

δ cy( *)=max min min v x δ v y δ v x∈Λ ∈Φ ( *, ) ∈Φ ( *, , )x y (8)

which is identical to:

δ η( *)=max v y, (9a)

cy Wy g Pδ Qv Rx yηSubject to : ≤min { : ≤ − *− − , ∈ }i i i i m3 +3 (9b)

i I=1, …, (9c)

v Hv g∈Λ = {{0, 1} : ≤ }m 24 (9d)

by leveraging on the countability of δ vΦ ( *, )x [66]. The right-hand sides of the constraints (9b) are pure linear

programming (LP) that can be replaced by equivalent KKT conditions, which are necessary and sufficient conditions for optimality of pure LP problems [25].

The equivalent monolithic MIP outer-layer subproblem is:

δ η( *)=max v y, (10a)

cyη i ISubject to : ≤ , =1, …i (10b)

Wy g Pδ Qv Rx i I≤ − *− − , =1, …i i3 (10c)

W λ c i I≤ , =1, …T i T (10d)

λ Wy g Pδ Qv Rx i I( − + *+ + )=0, =1, …i i i3 (10e)

y W λ c i I( − )=0, =1, …i T i T (10f)

y i I≥0, =1, …,i (10g)

λ i I≥0, =1, …,i (10h)

v Hv g∈Λ = {{0, 1} : ≤ }m 24 (10i)

where λi is the dual variable vector associated with condition Wy g Pδ Qv Rx≤ − *− −i i3 in (9b). Constraints (10c) and (10g), and (10d) and (10h) ensure primal and dual feasibility the right-hand LP of (9b), respectively. (10e) and (10f) are complementary slackness conditions, and can be linearized using the “Big-M” transformation [72]. For instance, the constraint (10f) is formulated as

y z M≤(1 − )i i (11a)

W λ c z M( − )≤T i T i (11b)

where zi is a vector of binary variables and M is a sufficiently large constant.

However, enumerating all the FSPs and listing the associated variables and constraints is not realistic. Moreover, it is likely that only a small set of the FSPs and the associated variables and constraints play a significant role in the solution. Therefore, a constraint-and-column generation algorithm [66] can be used to solve the FSP-enumeration-based MIP problem. The basic idea of this algorithm is that the outer-layer subproblem δ( *) (7) can be relaxed into problem δ( *), which is called inner-layer master problem, by a partial enumeration of the FSPs. The solution of δ( *) provides an upper bound to the outer-layer subproblem (7). Furthermore, a feasible solution to (7) can be obtained by solving its right-hand-side mini- mization, i.e. cymin

x y δ v, ∈Φ ( *, *) , where v* is any feasible solution of v, called

inner-layer subproblem. Problem (7) is a maximization, hence any feasible solution provides a lower bound to the optimum solution. Therefore, (7) can be solved by iteratively evaluating upper and lower bounds to the optimum solution through the inner-layer algorithm detailed in Table 1.

Table 1 The inner-layer algorithm, i.e. the algorithm used to solve the outer-layer subproblem.

Fix the lower bound LB = −∞, the upper bound UB = +∞, and the iteration counter k = 0. If k = 0 solve an inner-layer master problem of δ( *) in(10) without constraints(10b)-(10h), i.e., only with constraint(10i); otherwise, solve the following inner-layer master problem of δ( *) in(10) where xi is substituted by fixed parameter x *i which is the optimal solution obtained from Step 2, and i I= 1, …, is substituted by i k= 1,… , i.e. only a relevant subset of FSPs is considered:

δ η( *)=max v y, (12a)

b d f i where i k Subject to: (10 ), (10 ), (10 ) − (10 ) = 1, … (12b)

Wy g Pδ Qv Rx i k≤ − *− − *, =1, …i i3 (12c)

λ Wy g Pδ Qv Rx i k( − + *+ + *)=0, =1,…i i i3 (12d) Obtain the optimal objective value δ*( *) and optimal solution v*. Update the δUB= *( *). Solve the following inner-layer subproblem of δ( *), which corre- sponds to the δ vDRP( *, *) where v* is given by the solution in Step 1:

cymin x y δ v, ∈Φ ( *, *) (13a)

δ v x y Rx Wy g Pδ QvSubject to : Φ ( *, *)={( , )∈{0, 1} × : + ≤ − *− *}m m+ 32 3

(13b) Obtain the optimal solution (x y*, *) and optimal objective value cy*. Update the lower bound as cyLB {LB= max , * } If UB LB UB ε( − )/ ≤ , return the optimum solution v x y( *, *, * ) and terminate; otherwise, generate extra variables y λ,k k+1 +1 and add related constraints(12b)-(12d) by setting x x* ← *k+1 (where x* is the optimal solution obtained from Step 2) to δ( *) in(12). Update k k← + 1 and continue with Step 1.

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

166

The convergence proof and the analysis of the convergence proper- ties of this type of algorithms are provided in Zeng and Zhao [66]. Both the inner-layer master problem (12) in Step 1 and the inner-layer subproblem (13) in Step 2 are mixed integer linear programming problems and can be solved efficiently using standard branch-and-cut solvers, e.g. CPLEX [73].

3.3. Outer-layer master problem and the outer-layer algorithm

Adopting a similar method to the enumeration of FSPs, the full compact planner-attacker-defender problem (6) can be converted into its equivalent form by resorting to the countability of the attack set Λ, i.e. assuming that vΛ = { }j j

J =1 where J is the cardinality of Λ:

δ bya ρmin + + δ x y x y ρ, , , , ,

0 j j0 0 (14a)

δ Ex Fy gDSubject to : + + ≤0 0 1 (14b)

δ x y( , , )∈{0, 1} ×{0, 1} ×m m m0 0 +1 2 3 (14c)

cyρ j J≥ , =1, …,j (14d)

Rx Wy Pδ g Qv j J+ + ≤ − , =1, …,j j j3 (14e)

x y j J( , )∈{0, 1} × , =1, …,j j m m+2 3 (14f)

Finally, the outer-layer master problem of the planner-attacker- defender problem (6) is formulated into a MIP by a relaxation of (14) that partially enumerates Λ:

δ bya ρmin + + δ x y x y ρ, , , , ,

0 j j0 0 (15a)

b c Subject to: (14 ) − (14 ) (15b)

cyρ j k≥ , =1, …,j (15c)

Rx Wy Pδ g Qv j k+ + ≤ − *, =1, …,j j j3 (15d)

x y j k( , )∈{0, 1} × , =1, …,j j m m+2 3 (15e)

where v *j is the optimal value of the attacker’ decision, obtained from the solution of the outer-layer subproblem in Section 3.2. The integer k J< represents the partial enumeration of Λ. The optimization variables of the outer-layer master problem (15) are the investment decisions δ, the operating decisions x0 and y0 under nominal condi- tions, the operating decisions x j and y j in response to an attack, and the supplementary variable ρ, which provides the link to the inner- layer problem.

Finally, the planner-attacker-defender problem (1)–(3) is solved by combining the outer-layer master problem (15) and the outer-layer subproblem (7), via the constraint-and-column generation algorithm described in Table 2. Step 2 in Table 2 resorts to the algorithm described in Table 1 (Section 3.2) for the solution of the outer-layer

subproblem δ( *).

Table 2 Outer-layer algorithm.

1. Set LB = −∞, UB = +∞, and the iteration counter to k = 0. 2. If k = 0 solve the outer-layer master problem (15) without constraints (15c)-(15e);

otherwise, solve the complete version of the outer-layer master problem (15). Obtain the optimal solution * *δ x y ρ( *, , , *)0 0 and update the lower bound as

*aδ byLB ρ= *+ + *0 . 3. Solve the outer-layer subproblem δ( *) in(7) by calling the inner-layer algorithm

described inTable 1 using the optimal value δ* obtained in Step 1 as a parameter. Obtain the optimal solutions v x y( *, *, * ), and update the upper bound as

*aδ by cyUB {UB }=min , *+ + *0 4. If UB LB UB ε( − )/ ≤ , return * *δ x y v x y( *, , , *, *, * )0 0 and terminate; otherwise,

generate extra variables x y,k k+1 +1 and add related constraints(15c)-(15e) by setting *v v← *k+1 where v* is the optimal solution obtained from Step 2. Update k k← + 1 and continue with Step 1.

Fig. 2. IEEE 14-bus test system [74].

Table 3 Data for the existing transmission lines. Columns 2 and 3 show line reactance and capacity, respectively.

Branches B1/ l (Ohm) Pl L (MW)

1–2 0.05917 120 1–5 0.22304 60 2–3 0.19797 60 2–4 0.17632 60 2–5 0.17388 60 3–4 0.17103 60 4–5 0.04211 60 4–7 0.20912 60 4–9 0.55618 60 5–6 0.25202 60 6–11 0.1989 60 6–12 0.25581 60 6–13 0.13027 60 7–8 0.17615 60 7–9 0.11001 60 9–10 0.0845 60 9–14 0.27038 60 10–11 0.19207 60 12–13 0.19988 60 13–14 0.34802 60

Table 4 Data for the candidate lines for TEP, Columns 2 and 3 show line reactance and capacity, Column 4 provides annualized investment costs.

Branches B1/ l (Ohm) Pl L (MW) Annualized investment cost cl

b (M$)

1–12 0.25202 60 1.1 3–4 0.50618 60 1.3 4–10 0.20912 60 0.8 5–11 0.17615 60 0.7 9–14 0.55618 60 1.3

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

167

4. Case study

4.1. System data

The developed planner-attacker-defender framework is applied to the modified IEEE 14-bus system [74] (Fig. 2), which has 14 nodes connected by 20 transmission lines. Transmission line data are provided in Table 3. Candidate transmission lines for TEP are shown in Table 4.

The system includes 5 generators and 13 loads whose data are provided in Tables 5, 6, respectively. Each generator is characterized by generation capacity Pn

G and generation cost cn G. Similarly, each demand

node is characterized by the expected load Pn D and load shedding cost

cn LS. The total demand is 259 MW and the generation capacity is

620 MW. The discount parameter is σ=8760 h/y and allows considering the

same scale for the hourly-based nominal operating costs and for the annual investment costs. The discounted switch investment cost is 5 $/h per switch, which is small compared to the discounted transmis- sion line investment, e.g. the hourly investment cost for branch 1–12 is

125.6 $/h (Table 4 Row 2). The modified IEEE 14-bus system studied in this paper is repre-

sentative of small-size power systems, e.g. the 24-bus RTS system [75], the reduced representative Great Britain power network [76], etc. The original IEEE 14-bus test case represents a portion of the American electric power system (in the Midwestern US) as of February 1962 [77].

4.2. The impact of the investment budget on transmission expansion and switching

Table 7 presents the optimum investments in transmission expan- sion and switch installation for different levels of investment budget Πmax from $1 to $7 M, considering, without loss of generality, the case in which the maximum number of switchable lines is =3 , the attack budget is A =2max (the number of lines that can be simultaneously targeted), and α=0. 01, i.e. the network planner prioritizes system resilience quantified by the load shedding after the attack.

The nominal costs increase as the investment budget increases because additional lines and switches are installed. The new compo- nents reduce the operating costs and the attack loss simultaneously. In particular, the attack loss can be largely reduced from 34.2 to 0 MW, i.e. no load shedding after attack, if the nominal cost increases from $25.499 to $28.219 M; the marginal economic benefit of additional investments, i.e. savings in operating costs, decreases as the number of candidate lines and switches increases. Furthermore, the optimum set of switches to be installed in the small budget scenario is not necessarily a subset of the switches to be install in the large budget scenarios. For example, the switch 4–10 is installed for the optimum planning if Π =$5max M but it is replaced in the optimum plan by the switch 9–10 if Π =$7max M.

4.3. The benefits of line switching

Table 8 illustrates the benefit of transmission switching in terms of operating costs and attack losses for different numbers of switches K ∈ [0,3], Π =$7max M and A =3max . If there are no switches, the optimum system operating costs and attack losses are $26.343 M and 34.2 MW, respectively. If 1, 2 and 3 switches are installed, the operating costs decrease to $23.891, $22.927 and $23.961 M, respectively, leading to 9.31%, 12.97% and 9.04% savings with respect to the no-switch scenario. More notably, the attack losses decrease significantly owing to additional switches (Table 8 Row 6) from 26.7 MW when only one switch is allowed (K = 1) to 22.0 MW and 13.5 MW, respectively, when 2 and 3 switches are installed. The set of expanded lines is consistent for the three cases in which switches are also installed (Table 8 Columns 3–5). Furthermore, the switching capability leads to a reduction in load shedding of 17.60% and 49.44% for K = 2 and K = 3, respectively, as compared to K = 1. At the same time, the investment costs increase by only 0.24% and 0.48%, i.e. from $3.709 to $3.718 and $3.726 M.

Fig. 3(a) shows the optimal power flow pattern under normal operating conditions after applying the optimum transmission capacity expansion and switch installation for K = 1, A =3max , Π =$7max M in

Table 5 Data for generators, Columns 2 and 3 show generation capacity and generation cost, respectively.

Generator n Pn G (MW) cn

G ($/MWh)

1 250 10 2 200 11 3 60 22 6 50 21 8 60 20

Table 6 Data for demand nodes , Columns 2 and 3 show expected load values and load shedding cost, respectively.

Demand n Pn D (MW) cn

LS ($/MWh)

2 21.7 50 3 94.2 50 4 47.8 50 5 7.6 50 6 11.2 50 7 0 50 8 0 50 9 29.5 50 10 9 50 11 3.5 50 12 6.1 50 13 13.5 50 14 14.9 50

Table 7 Optimum investment when K = 3, A =2max and α=0. 01. Column 2 shows the nominal costs, i.e. the sum of annualized operating costs (Column 3) and investment costs. Column 4 shows the load shedding following the attack. Columns 5 and 6 identify the optimal investment decision, i.e. the new transmission lines to be built and switches to be installed.

Πmax

(M$) Nominal costs (M$)

Operating costs (M$)

Attack loss (MW)

Installed lines

Installed switches

1 25.499 25.490 34.2 – 7–9 3 25.340 22.968 14.9 1–12,3–4 4–7,4–9 5 27.483 22.928 3.5 1–12,4–

10,9–14,3–4 4–7,4–9,4– 10

7 28.219 22.927 0 1–12,4– 10,5–11,9– 14,3–4

4–7,4–9,9– 10

Table 8 Optimum system costs and attack loss for a different number of switches (K ) in the scenario A =3max and Π =$7max M.

No switch K = 1 K = 2 K = 3

Installed lines 1–12,5–11 1–12,3–4,9– 14

1–12,3–4,9– 14

1–12,3–4,9– 14

Installed switches – 4–5 4–9,7–9 1–2,1–5,5–6 Investment (M$) 1.800 3.709 3.718 3.726 Operating cost (M

$) 26.343 23.891 22.927 23.961

Attack loss (MW) 34.2 26.7 22.0 13.5

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

168

Table 8. Lines 1–12, 3–4, 9–14 are added to the original network, and the switch installed in line 4–5 is switched on for economic power dispatch in nominal operating conditions. Fig. 3(b) shows the optimal power flow pattern after the defender's corrective actions in response to the attack targeting lines 2–3, 2–4, 7–8. Line 4–5 is switched off for power flow re-dispatching, resulting in a system load shedding of 26.7 MW. For comparison, Fig. 3(c) shows the optimum flow pattern after the same attack as in Fig. 3(b) if the switch in line 4–5 is not installed. In this case, the attack results in system load shedding of 42.3 MW, i.e. the switch in line 4–5 entails an attack loss reduction of 15.6 MW (36.85%).

4.4. Sensitivity analysis for different attack scenarios

It is usually challenging for system planners to predict the time, location and extent of an attack. Instead, they aim at designing the network as resilient as possible by identifying investment decisions that perform well in the foreseen scenarios. To this end, we consider the performance of the optimal solution under different attack scenarios, i.e. under different attack budget values Amax. Six attack scenarios are considered, i.e. A =1,2, 3, 4, 5, 6max . The candidate lines for the TEP are reported in Table 4 and the maximum number of switchable lines is 3, i.e. K = 3. The results are shown in Tables 9 and 10 for two different levels of investment budget Π =$3max M, and Π =$7max M, respectively.

Tables 9 and 10 show the attack loss and the regret when an optimal investment strategy is realized based on a foreseen attack scenario A

∼max (planned scenario), and a particular attack scenario Amax

(actual scenario) actually occurs. The regret of an investment decision under a planned scenario given the actual scenario is quantified as the difference between the attack loss for the planned scenario A

∼max and

the minimum attack loss that results if the network planner has prior knowledge of the actual scenario Amax. Regret is a well-established measure of risk in decision making under uncertainty (Bell, 1985). The attack loss values in Tables 9 and 10 show that the system configura- tion is optimized for the planned attack scenario, i.e. the minimum attack loss occurs if A A=

∼max max, and increases if A A≠ ∼max max. In

particular, the planner/defender cannot protect the system against large planned attack scenarios, i.e. A =6

∼max , under the current assump-

tions of K , Πmax and candidate lines. Therefore, the minimum objective function is achieved by minimizing the investment costs, and the attack loss amounts at the same value as when the small planned attack scenario, i.e. A =1

∼max , is expected. Tables 9 and 10, Columns 8 and 9

show the maximum and the average regret across the six attack scenarios. Optimum solutions obtained assuming small, i.e. A =1

∼max ,

and large, i.e. A =6 ∼max

, attacks can be highly regretful if other attacks occur, resulting in an average regret of 7.2 MW and 6.8 MW, respec- tively when Π =$3max M (Tables 9 Row 3 and 8), and an average regret of 12.9 MW and 11.8 MW, respectively when Π =$7max M (Table 10 Row 3 and 8). The best solutions in terms of maximum and average regret are obtained if A =2

∼max when Π =$7max M, and if A =2

∼max or 3 when

Π =$3max M. Therefore, TE and TS investment planning for A =2 ∼max

is overall a more robust strategy for the considered network.

The impact of the set of candidate lines on the maximum and average regret solutions is investigated by adding lines 2–6, 3–5, 8–9 to the candidate lines of Table 4. The results are shown in Tables 11, 12 for two different levels of investment budget Π =$3max M, and Π =$10max M, respectively.

Similar to Tables 9 and 10, the attack loss values in Table 11, 12 show that the system configuration is optimized for the planned attack scenario, i.e. the minimum attack loss occurs if A A=

∼max max, and increases if A A≠

∼max max. On the other hand, the system planner/ defender can exploit the additional flexibility provided by the extended set of candidate lines and, therefore, assuming large planned attack scenarios results in more resilient system configurations, i.e. the attack

Fig. 3. The optimum power flow pattern in normal operation condition (a), the optimum flow pattern after defender's corrective action in response to attack targeting lines 2–3, 2–4, 7–8 (b), and the optimum flow pattern after defender's corrective action if no switch is installed in line 4–5 (c), for K = 1, A =3max and Π =$7max M. The squares represent power generators and the circles represent demand nodes. The width of lines indicates the amount of power flow and the arrows denote the direction of the flow. Dotted lines represent failed branches removed due to the attack. White circles represent switching devices.

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

169

loss are smaller compared to Tables 9 and 10. Furthermore, large values of investment budget, i.e. Π =$10max M in Table 12, result in more resilient configurations as compared to Π =$3max M in Table 11, because of the extended set of candidates line that can be built for TE. In particular, the best solutions are obtained if A =4,5,6

∼max in terms of

both maximum and average regret when Π =$3max M (Table 11 Row 6, 7, 8), and if A =6

∼max (in terms of maximum regret) or A =5

∼max (in terms

of average regret) when Π =$10max M (Table 12 Row 7 and 8). Therefore, robust strategies are sensitive to the planning flexibility, i.e. assuming small planned attack scenarios can be a robust strategy if the planning is subject to many constraints and limited investment budget, and, on the other hand, assuming large planned attack scenarios can be a robust strategy if the planning can resort to a full set of candidate lines and large investment budget. This type of sensitivity analysis provides system planners a useful tool to identify attack scenario to assume that leads to robust investment decision- making.

4.5. Optimum expansion and switching for different planner's preferences

The parameter α models the planner propensity towards more profitable system planning and operations or towards more resilient

system planning. Large values of α characterize a system planner concerned by resilience issues at the expenses of large nominal costs. In contrast, small values of α imply large attack loss risk and small nominal costs. Fig. 4 plots the attack loss as a function of α for different values of the investment and attack budgets, and K = 3. As α increases, the attack loss decreases because more weight is placed on the attack- related objective in Eq. (1a); therefore, an increased number of transmission lines and switches is built.

Fig. 5 represents the efficient frontier of this optimization problem, i.e. the level of attack loss versus the nominal costs of the optimum planning for different values of α, A =2max and Π =$7max M. Fig. 5 provides relevant information on the tradeoff between cost minimiza- tion and mitigation of the attack risk. For a system planner interested solely in cost minimization (α = 1 × 10−3) the level of risk in attack loss is 34.2 MW with a total cost of $24.38 M. On the other hand, for a network planner interested exclusively in the mitigation of risk in attack loss (α = 5 × 10−3), the attack loss can be reduced to 0 MW with a total cost of $28.30 M. Therefore, the efficient frontier is particularly helpful in guiding the system planner's tradeoff between total invest- ment costs and the reduction of risks stemming from attacks.

Table 9 Cross-comparison of optimum investment plans for α = 0. 01 and Π =$3max M.

Planned scenario A ∼max Actual scenario Amax Max. regret (MW) Avg. regret (MW)

1 2 3 4 5 6

Attack loss/Regret (MW/MW)

1 0/0 34.2/19.3 34.2/5.8 56.9/7.8 82/6.6 138.9/3.5 19.3 7.2 2 0/0 14.9/0 28.4/0 56.9/7.8 82/6.6 138.9/3.5 7.8 3 3 0/0 14.9/0 28.4/0 56.9/7.8 82/6.6 138.9/3.5 7.8 3 4 0/0 34.2/19.3 34.2/5.8 49.1/0 78.9/3.5 138.9/3.5 19.3 5.4 5 0/0 34.2/19.3 34.2/5.8 49.1/0 75.4/0 135.4/0 19.3 4.2 6 0/0 34.2/19.3 34.2/5.8 53.4/9 82/6.6 135.4/0 19.3 6.8

Table 10 Cross-comparison of optimum investment plans for α=0. 01 and Π =$7max M.

Planned scenario A ∼max Actual scenario Amax Max. regret (MW) Avg. regret (MW)

1 2 3 4 5 6

Attack loss/Regret (MW/MW)

1 0/0 34.2/34.2 34.2/20.7 56.9/12.5 82/6.6 138.9/3.5 34.2 12.9 2 0/0 0/0 13.5/0 44.4/0 75.4/0 135.4/0 0 0 3 0/0 12.5/12.5 13.5/0 56.9/12.5 82/6.6 138.9/3.5 12.5 5.9 4 0/0 14.9/14.9 28.4/14.9 44.4/0 78.9/3.5 138.9/3.5 14.9 6.1 5 0/0 34.2/34.2 34.2/20.7 49.1/4.7 75.4/0 135.4/0 34.2 9.9 6 0/0 34.2/34.2 34.2/20.7 53.4/9.0 82/6.6 135.4/0 34.2 11.8

Table 11 Cross-comparison of optimum investment plans for α=0. 01 and Π =$3max M when the set of candidate lines is extended.

Planned scenario A ∼max Actual scenario Amax Max. regret (MW) Avg. regret (MW)

1 2 3 4 5 6

Attack loss/Regret (MW/MW)

1 0/0 34.2/28.1 34.2/14.6 56.9/28.5 82/34.2 138.9/77.7 77.7 30.5 2 0/0 6.1/0 34.4/14.8 67.3/38.9 127.3/79.5 127.3/66.1 79.5 33.2 3 0/0 9/2.9 19.6/0 67.3/38.9 127.3/79.5 127.3/66.1 79.5 31.2 4 0/0 14.9/8.8 28.4/8.8 28.4/0 47.8/0 61.2/0 8.8 2.9 5 0/0 14.9/8.8 28.4/8.8 28.4/0 47.8/0 61.2/0 8.8 2.9 6 0/0 14.9/8.8 28.4/8.8 28.4/0 47.8/0 61.2/0 8.8 2.9

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

170

4.6. Computational performance of the solution methodology

This case study is implemented with Optimization Programming Language [78] and solved by CPLEX 12.6.1 [73] on an Intel i7-4790 with 2 Quad-Core processors running at 3.6 GHz and 16 GB of RAM. The two-layer constraint-and-column generation methodology de- scribed in Section 3 is run until convergence, enforcing a tolerance level ϵ = 10−5 % for the outer and the inner layer algorithms. In addition, the MIP solver parameters in CPLEX are set as follows: MIP relative gap tolerance epgap=10−5; MIP emphasis switch mipemphasis=1, i.e. feasibility is emphasized over optimality, and more effort is spent in immediately beginning computations that search for early (and then improved) feasible solutions while less effort is applied to the model analyses that aid in the eventual proof of optimality.

Table 13 shows the computational performance of the optimization algorithm applied to the case study in Section 4. Although the number of iterations is generally small, the computation time differs greatly across various instances, because the maximum switchable lines K and investment budget Πmax largely affect the feasibility region (solution space) of outer-layer master problem (15), and the attack budget Amax

governs the feasibility region (solution space) of inner-layer master problem δ( *) in (12). The two MIP problems (12) and (15) are the most computationally demanding steps of the proposed method. In particular, the computational time increases significantly with respect to the maximum switchable lines K , especially for the case A =2max and Π =$7max M, which highlights the necessity of applying the upper bound constraint (1c) that limits the number of installed switches .

To reduce the computational time a dynamic MIP gap strategy is implemented in the solution of the outer-layer master problem (15), which leverages on the fact that any feasible solution of (15) provides a lower bound LB to the objective if the optimality gap UB LB UB( − )/ of the solution in the outer-layer algorithm is large; in this case it is not necessary to prove optimality of the master problem (15). Therefore, a large MIP relative gap tolerance epgap can be applied for solving the master problem (15) at the initial iterations of the algorithm, and small epgap values are enforced when the outer-layer algorithm approaches convergence, i.e. the gap UB LB UB( − )/ becomes smaller than the

Table 12 Cross-comparison of optimum investment plans for α=0. 01 and Π =$10max M when the set of candidate lines is extended.

Planned scenario A ∼max Actual scenario Amax Max. regret (MW) Avg. regret (MW)

1 2 3 4 5 6

Attack loss/Regret (MW/MW)

1 0/0 34.2/34.2 34.2/20.7 56.9/43.4 82/66.6 138.9/110 110 45.8 2 0/0 0/0 13.5/0 44.4/30.9 67.3/51.9 101.2/72.3 72.3 25.9 3 0/0 12.5/12.5 13.5/0 56.9/43.4 70.4/55 104.7/75.8 75.8 31.1 4 0/0 12.5/12.5 13.5/0 13.5/0 47.8/32.4 61.2/32.3 32.4 12.9 5 0/0 0/0 13.5/0 13.5/0 15.4/0 61.2/32.3 32.3 5.4 6 0/0 14.9/14.9 28.4/14.9 28.4/14.9 28.4/13 28.9/0 14.9 9.6

Fig. 4. Attack loss versus α for different attack and investment budgets where K = 3.

Fig. 5. Efficient frontier for different values of α, A =2max and Π =$7max M.

Table 13 Computational performance of the optimization algorithm. Each row corresponds to a given combination of the attack budget Amax, the investment budget Πmax and the maximum number of switchable lines K . Number of iterations, computational time, solution gaps for sub-optimal cases are shown in Columns 4, 5 and 6, respectively.

Amax Πmax M$ K # of Iterations (avg. inner iteration)

Time (s) Solution Gap (%)

2 3 2 4 (2) 3.3 0 4 4 (2.3) 8.8 0 6 4 (2) 20.7 0

7 2 6 (2) 20.6 0 4 6 (2.2) 3.1e3 0 6 ≥6 >3.6e3 5.97

4 3 2 4 (2.8) 10.9 0 4 4 (3) 18.5 0 6 4 (2.8) 21.1 0

7 2 5 (2.4) 13.8 0 4 5 (3) 37.4 0 6 5 (3) 56.9 0

6 3 2 3 (2.5) 2.4 0 4 3 (2.5) 3.2 0 6 3 (2.5) 66.4 0

7 2 3 (2) 2.5 0 4 3 (2.5) 4.1 0 6 3 (2.5) 6.9 0

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

171

defined threshold, e.g. 5%. By the same token, the dynamic MIP gap strategy can be implemented to solve the master problem (12) in the inner-layer algorithm.

Fig. 6 compares the convergence processes when a constant MIP gap strategy, i.e. epgap=10−5, and a dynamic MIP gap strategy is applied, i.e. epgap=5.0∙10−5in the first 4 iterations and epgap=10−5in the last two iterations, for the case A =2max , Π =$7max M and K = 4 (Table 13 Row 6). The solution process of the dynamic MIP gap strategy is very similar to that of the constant MIP gap strategy, except that the lower bound is slightly larger at the third iteration in the dynamic MIP gap strategy, as indicated in Fig. 6. The dynamic MIP gap strategy achieves optimum solutions with reduced computation time from 3066 s to 113 s, i.e. 96.31% reduction. Furthermore, the compu- tational worst case A =2max , Π =$7max M and K = 6 (Table 13 Row 7) for which an optimality gap UB LB UB( − )/ =5.97% persists after running the optimization for one hour, can be solved to optimality, i.e. UB LB UB( − )/ =0%, in 216 s by applying the dynamic MIP gap strategy, i.e. epgap = 5.0∙10−3 in the first 4 iterations and 10−5 in the last two iterations.

The computational time required for the application of the pro- posed solution algorithm increases exponentially with the size of the network under investigation [67]. Nonetheless, the proposed planning problem can be solved off-line and the issue of CPU time can be tackled by allowing adequate computational time. Furthermore, the computa- tional complexity can be decreased through sophisticated approaches, i.e. using relevant heuristics and efficient algorithms to solve the two master (MIP) problems in the outer and inner layers. Such develop- ments can be investigated in future works.

5. Conclusions

This paper presents a trilevel planner-attacker-defender model to identify optimum combined investment plans of capacity expansion and switch installation in electric power systems. Transmission switch- ing is employed to mitigate the impact of disruptive events on system functionality. The model bridges the gap between long-term system planning for transmission expansion and short-term switching opera- tions in response to attacks. The optimum investment plan minimizes the weighted sum of the nominal costs, i.e. investment and operating costs, and the maximum loss of functionality after the deliberate attacks. The proposed formulation configures a min-max-min optimi- zation with discrete variables in the three levels, which is computa- tionally challenging. The problem is solved by reformulating the third level MIP problem and adopting a two-layer constraint-and-column generation method, where a cutting plane decomposition strategy

based on primal cuts is applied in each layer. The computation time of the solution algorithm is considerable even when the problem size is relatively small due to its complexity. However, the computational performance can be enhanced by adopting the dynamic MIP gap strategy, which can reduce the computational time by approximately 96% in certain cases.

The application to a case study shows that the negative impact of an attack on ETNs can be mitigated by installing selected transmission lines and advanced switching devices at the expense of increased investment resources. In particular, the loss of system functionality after the attack and the operating costs can be decreased by up to 50% and 13%, respectively, by installing switches on transmission lines and at the same time the investment costs increase by 0.5%. Furthermore, the sensitivity analysis of the optimum solution with respect to uncertain attack scenarios provides network planners valuable infor- mation on the attack scenario to assume in the planning phase. The results show that robust strategies are dependent on the planning flexibility. Designing the system against small planned attack scenarios is a robust strategy if the planning is subject to many constraints on the new lines that can be built and a limited investment budget is available. Conversely, designing the system against large planned attack scenar- ios is a robust strategy if the planner can select the new lines to be built among a full set of candidate lines and a large investment budget is available. Finally, the efficient frontier of the optimum solutions identifies the tradeoff between nominal costs and attack losses for a fixed investment budget. System planners can use this frontier to make investment decisions which address system economics and resilience to disruptions.

Acknowledgements

The authors acknowledge the CTI - Commission for Technology and Innovation (CH), and the SCCER-FURIES - Swiss Competence Center for Energy Research - Future Swiss Electrical Infrastructure, for their financial and technical support to the research activity presented in this paper.

References

[1] Kröger W, Zio E. Vulnerable systems. Springer Science & Business Media; 2011. [2] Zio E. Reliability engineering: old problems and new challenges. Reliab Eng Syst Saf

2009;94(2):125–41. [3] Communications, F.D.o.t.E.T.E.a., Energieperspektiven 2050; 2013. [4] Winter C. Germany reaches new levels of greendom, gets 31 percent of its electricity

from renewables. Bus Week 2014;14. [5] Lehr U, Lutz C, Edler D. Green jobs? Economic impacts of renewable energy in

Germany. Energy Policy 2012;47:358–64. [6] Amin SM, Wollenberg BF. Toward a smart grid: power delivery for the 21st century.

IEEE Power Energy Mag 2005;3(5):34–41. [7] Cadini F, Zio E, Petrescu C-A. Optimal expansion of an existing electrical power

transmission network by multi-objective genetic algorithms. Reliab Eng Syst Saf 2010;95(3):173–81.

[8] Garver LL. Transmission network estimation using linear programming. IEEE Trans Power Appar Syst 1970(7):1688–97.

[9] Villasana R, Garver L, Salon S. Transmission network planning using linear programming. IEEE Trans Power Appar Syst 1985(2):349–56.

[10] Pereira MV, Pinto LM. Application of sensitivity analysis of load supplying capability to interactive transmission expansion planning. IEEE Trans Power Appar Syst 1985(2):381–9.

[11] Seifu A, Salon S, List G. Optimization of transmission line planning including security constraints. IEEE Trans Power Syst 1989;4(4):1507–13.

[12] Bahiense L, Oliveira GC, Pereira M, Granville S. A mixed integer disjunctive model for transmission network expansion. IEEE Trans Power Syst 2001;16(3):560–5.

[13] Alguacil N, Motto AL, Conejo AJ. Transmission expansion planning: a mixed- integer LP approach. IEEE Trans Power Syst 2003;18(3):1070–7.

[14] Dusonchet Y, El-Abiad A. Transmission planning using discrete dynamic optimiz- ing. IEEE Trans Power Appar Syst 1973(4):1358–71.

[15] Al-Hamouz ZM, Al-Faraj AS. Transmission-expansion planning based on anon- linear programming algorithm. Appl Energy 2003;76(1):169–77.

[16] Romero R, Monticelli A. A hierarchical decomposition approach for transmission network expansion planning. IEEE Trans Power Syst 1994;9(1):373–80.

[17] Latorre G, Cruz RD, Areiza JM, Villegas A. Classification of publications and models on transmission expansion planning. IEEE Trans Power Syst 2003;18(2):938–46.

[18] Romero R, Monticelli A, Garcia A, Haffner S. Test systems and mathematical

Fig. 6. Upper bound (UB) and lower bound (LB) of the optimal solution vs. iteration step for A =2max , Π =$7max M and K = 4 when a constant MIP gap strategy, i.e. epgap=10−5, is applied (filled squares/circles and solid line) and a dynamic MIP gap strategy, i.e. epgap=5.0∙10−3 in the first 4 iterations and epgap=10−5 in the last two iterations, is applied (empty squares/circles and dotted line).

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

172

models for transmission network expansion planning. IEE Proc Gener Transm Distrib 2002, [IET].

[19] de Dios R, Soto F, Conejo AJ. Planning to expand?. IEEE Power Energy Mag 2007;5(5):64–70.

[20] Choi J, et al. A method for transmission system expansion planning considering probabilistic reliability criteria. Power Syst, IEEE Trans on 2005;20(3):1606–15.

[21] Silva IJ, Rider MJ, Romero R, Murari CA. Transmission network expansion planning considering uncertainty in demand. IEEE Trans Power Syst 2006;21(4):1565–73.

[22] de la Torre S, Conejo AJ, Contreras J. Transmission expansion planning in electricity markets. IEEE Trans Power Syst 2008;23(1):238–48.

[23] Villumsen JC, Philpott AB. Investment in electricity networks with transmission switching. Eur J Oper Res 2012;222(2):377–85.

[24] Jabr RA. Robust transmission network expansion planning with uncertain renew- able generation and loads. IEEE Trans Power Syst 2013;28(4):4558–67.

[25] Ruiz C, Conejo AJ. Robust transmission expansion planning. Eur J Oper Res 2015;242(2):390–401.

[26] Sorokin A, Portela J, Pardalos PM. Algorithms and models for transmission expansion planningHandbook of networks in power systems I. Springer; 2012. p. 395–433.

[27] Hemmati R, Hooshmand R-A, Khodabakhshian A. State-of-the-art of transmission expansion planning: comprehensive review. Renew Sustain Energy Rev 2013;23:312–9.

[28] National Research Council . Physical security considerations for electric power systemsTerrorism and the electric power delivery system. Washington, DC: National Academy Press; 2012.

[29] National Research Council . Making the nation safer: the role of science and technology in countering terrorism. Washington, DC: The National Academies Press; 2002.

[30] Linkov I, et al. Changing the resilience paradigm. Nat Clim Change 2014;4(6):407–9.

[31] Fang YP, Pedroni N, Zio E. Resilience-based component importance measures for critical infrastructure network systems. IEEE Trans Reliab 2016;65(2):502–12.

[32] Haimes YY, Longstaff T. The role of risk analysis in the protection of critical infrastructures against terrorism. Risk Anal 2002;22(3):439–44.

[33] Barker K, Santos JR. A risk‐based approach for identifying key economic and infrastructure systems. Risk Anal 2010;30(6):962–74.

[34] Hausken K. Strategic defense and attack for reliability systems. Reliab Eng Syst Saf 2008;93(11):1740–50.

[35] Patterson SA, Apostolakis GE. Identification of critical locations across multiple infrastructures for terrorist actions. Reliab Eng Syst Saf 2007;92(9):1183–203.

[36] Levitin G, Ben-Haim H. Importance of protections against intentional attacks. Reliab Eng Syst Saf 2008;93(4):639–46.

[37] Carrión M, Arroyo JM, Alguacil N. Vulnerability-constrained transmission expan- sion planning: a stochastic programming approach. IEEE Trans Power Syst 2007;22(4):1436–45.

[38] Alguacil N, Arroyo JM, Carrión M. Transmission network expansion planning under deliberate outagesHandbook of power systems I. Springer; 2010. p. 365–89.

[39] Arroyo JM, Alguacil N, Carrión M. A risk-based approach for transmission network expansion planning under deliberate outages. IEEE Trans Power Syst 2010;25(3):1759–66.

[40] Salmeron J, Wood K, Baldick R. Analysis of electric grid security under terrorist threat. IEEE Trans Power Syst 2004;19(2):905–12.

[41] Cox LAT. Jr, Some limitations of “Risk=Threat×Vulnerability×Consequence” for risk analysis of terrorist attacks. Risk Anal 2008;28(6):1749–61.

[42] Brown GG, Cox LAT. Jr, How probabilistic risk assessment can mislead terrorism risk analysts. Risk Anal 2011;31(2):196–204.

[43] Brown G, Cox L. Making terrorism risk analysis less harmful and more useful: another try (Response). Risk Anal 2011;31(2):193–5.

[44] Guikema SD, Aven T. Assessing risk from intelligent attacks: a perspective on approaches. Reliab Eng Syst Saf 2010;95(5):478–83.

[45] Amin M. Toward self-healing energy infrastructure systems. IEEE Comput Appl Power 2001;14(1):20–8.

[46] Quattrociocchi W, Caldarelli G, Scala A. Self-healing networks: redundancy and structure. PloS One 2014;9(2):e87986.

[47] Han J, Papavasiliou A. The impacts of transmission topology control on the European Electricity Network. IEEE Trans Power Syst 2016;31(1):496–507.

[48] Rolim JG, Machado LJB. A study of the use of corrective switching in transmission

systems. IEEE Trans Power Syst 1999;14(1):336–41. [49] Miu KN, Chiang H-D, Yuan B, Darling G. Fast service restoration for large-scale

distribution systems with priority customers and constraints. IEEE Trans Power Syst 1998;13(3):789–95.

[50] Escobedo AR, Moreno-Centeno E, Hedman KW. Topology control for load shed recovery. IEEE Trans Power Syst 2014;29(2):908–16.

[51] Hedman KW, Oren SS, O’Neill RP. Optimal transmission switching: economic efficiency and market implications. J Regul Econ 2011;40(2):111–40.

[52] Sahraei-Ardakani M, et al. Real-time contingency analysis with transmission switching on real power system data. IEEE Trans Power Syst 2015;99:1–2.

[53] Fisher EB, Neill RP, Ferris MC. Optimal transmission switching. IEEE Trans Power Syst 2008;23(3):1346–55.

[54] Villumsen JC, Bronmo G, Philpott AB. Line capacity expansion and transmission switching in power systems with large-scale wind power. IEEE Trans Power Syst 2013;28(2):731–9.

[55] Salehizadeh MR, Rahimi-Kian A, Hausken K. A leader–follower game on conges- tion management in power systemsGame theoretic analysis of congestion, safety and security. Springer; 2015. p. 81–112.

[56] Bier VM, et al. Methodology for identifying near-optimal interdiction strategies for a power transmission system. Reliab Eng Syst Saf 2007;92(9):1155–61.

[57] Yao Y, Edmunds T, Papageorgiou D, Alvarez R. Trilevel optimization in power network defense. IEEE Trans Syst, Man, Cybern, Part C: Appl Rev 2007;37(4):712–8.

[58] Yuan W, Zhao L, Zeng B. Optimal power grid protection through a defender– attacker–defender model. Reliab Eng Syst Saf 2014;121:83–9.

[59] Brown G, Carlyle M, Salmerón J, Wood K. Defending critical infrastructure. Interfaces 2006;36(6):530–44.

[60] Alguacil N, Delgadillo A, Arroyo JM. A trilevel programming approach for electric grid defense planning. Comput Oper Res 2014;41:282–90.

[61] Alderson DL, Brown GG, Carlyle WM. Operational models of infrastructure resilience. Risk Anal 2015;35(4):562–86.

[62] Hausken K, Levitin G. Minmax defense strategy for complex multi-state systems. Reliab Eng Syst Saf 2009;94(2):577–87.

[63] Hausken K, Levitin G. Review of systems defense and attack models. Int J Perform Eng 2012;8(4):355–66.

[64] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 1992;13(5):1194–217.

[65] Bertsimas D, et al. Adaptive robust optimization for the security constrained unit commitment problem. IEEE Trans Power Syst 2013;28(1):52–63.

[66] Zeng B, Zhao L. Solving two-stage robust optimization problems using a column- and-constraint generation method. Oper Res Lett 2013;41(5):457–61.

[67] Zeng B, An Y. Solving bilevel mixed integer program by reformulations and decomposition [Technical report]. Department of Industrial and Management Systems Engineering, University of South Florida; 2014.

[68] Fang Y-P, Pedroni N, Zio E. Optimal capacity allocation for a failure resilient electrical infrastructure. DSM 2014 2014.

[69] Boyer SA. SCADA: supervisory control and data acquisition. International Society of Automation; 2009.

[70] Woods DD. Four concepts for resilience and the implications for the future of resilience engineering. Reliab Eng Syst Saf 2015;141:5–9.

[71] Thiele A, Terry T, Epelman M. Robust linear optimization with recourse. Rapport technique 2009:4–37.

[72] Fortuny-Amat J, McCarl B. A representation and economic interpretation of a two- level programming problem. J Oper Res Soc 1981:783–92.

[73] IBM ILOG CPLEX V12.1 User’s Manual for CPLEX. Incline Village, NY, USA; 2009. [74] Xu Z, Dong Z, Wong K. Transmission planning in a deregulated environment. IEE

Proc Gener Transm Distrib 2006. [75] Grigg C, et al. The IEEE reliability test system-1996. A report prepared by the

reliability test system task force of the application of probability methods subcommittee. IEEE Trans Power Syst 1999;14(3):1010–20.

[76] Bell KW. Test system requirements for modelling future power systems. In: IEEE PES General Meeting; 2010.

[77] Washington, U.o. Power Systems Test Case Archive. [cited 2016 1 September]; Available from: ⟨http://www.ee.washington.edu/research/pstca/pf14/pg_ tca14bus.htm⟩.

[78] Van Hentenryck P. The OPL optimization programming language. MIT Press; 1999.

Y. Fang, G. Sansavini Reliability Engineering and System Safety 159 (2017) 161–173

173