Alternating Current (AC) Power Flow Analysis in an

Electrical Power Network

Cross Reference to Related Application

The present application claims priority from Australian Provisional Application No. 20129021 18, the content of which is incorporated by reference.

Technical Field

This disclosure generally concerns electrical power networks, and more particularly, a computer-implemented method for AC power flow analysis in an electrical power network. This disclosure also concerns a computer system, a computer program and an electrical power network employing the method.

Background

Optimization technology is ubiquitous in modern power systems and resulted in cost savings. However, the increasing role of demand response, the integration of renewable sources of energy, and the desire for more automation in fault detection and recovery pose new challenges for the planning and control of electrical power systems. Power grids now need to operate in more stochastic environments and under varying operating conditions, while still ensuring system reliability and security.

Summary

According to a first aspect, there is provided a computer-implemented method for alternating current (AC) power flow analysis in an electrical power network, the method comprising:

(a) based on information relating to buses and transmission lines connecting the buses in the electrical power network, determining a convex approximation of AC power flows in the electrical power network,

wherein the convex approximation of the AC power flows comprises convex approximation of nonlinear cosine terms associated with active power components and reactive power components of the AC power flows; and (b) optimising a convex objective function associated with the electrical power network using the convex approximation of the AC power flows.

In one example, convex approximation in (a) may comprise linear programming approximation of the AC power flows, wherein linear approximation of cosine terms associated with the active power components and reactive power components are determined; and optimisation in (b) based on a set of nonlinear constraints that comprises the linear approximation of cosine terms. In this case:

A piecewise linear approximation of the cosine terms may be used, and the set of nonlinear constraints includes a set of linear inequalities obtained from the piecewise linear approximation.

The set of nonlinear constraints associated with the reactive power components may be determined by: expressing voltage magnitudes as variations from fixed magnitudes, and separating the nonlinear terms into the sum of a first part involving only the fixed magnitudes and linearized in (b) and of a second part involving the variations which is linearized using Taylor expansion of the nonlinear terms using the variations.

In another example, convex approximation in (a) may comprise convex quadratic programming approximation of the AC power flows, wherein second-order series approximation of cosine terms associated with the active power components and reactive power components are determined; and optimisation in (b) is based on a set of nonlinear constraints that includes the second-order series approximation of cosine terms. In this case:

The series approximation may be second-order Taylor series approximation of the cosine terms. The active power components and reactive power components may be defined using convex approximation of power loss terms relating to power loss on the transmission lines connecting the buses in the electrical power network. The active power components and reactive power components may further include a linear outer-approximation of voltage square terms in the components.

The set of nonlinear constraints may further comprise variables to relax the square of the voltage magnitude and phase angel difference terms associated with the active power components and reactive power components, and to define a convex feasible region.

The optimisation in (b) may be for any suitable application. Some examples are provided below:

In an AC power flow application, (i) the objective function in (b) may be associated with the convex approximation of the cosine terms associated with the active power components and reactive power components; and (ii) optimising the objective function maximizes the convex approximation of the cosine terms.

In a power restoration application, (i) the objective function may be associated with a served load of the electrical power network; and (ii) optimising the objective function maximises the served load to further determine one or more of: generation of active power at each bus, generation of reactive power at each bus and a. maximised served load. In this case, optimisation of the objective function in (ii) may be based on nonlinear constraints associated with active power generation, and desired active load and desired reactive load at each bus.

In a capacitor placement application, (i) the objective function may be associated with a number of capacitors for placement in the electrical power network; and

(ii) optimising the objective function optimises the number of capacitors placed in the electrical power network. In this case, optimisation of the objective function in (ii) may be based on nonlinear constraints associated with one or more of: desired voltage limit, capacitor injection variables, and reactive , generation limits of generators.

In an AC optimal power flow application, (i) the objective function may be associated with a cost of generating electricity in the electrical power network; and (ii) optimising the objective function minimises the cost of generating electricity in the electrical power network.

Further, convex approximation of the AC power flows may further comprise convex approximation of sine terms associated with active power components and reactive power components of the AC power flows. The optimisation in (b) may be based on nonlinear constraints relating to the reactive power components, the nonlinear constraints being determined by: setting conductance (g) values set to zero; or setting cosine terms set to unity, and using non-zero conductance (g) values. The optimisation in (b) may be based on constraints relating to one or more of:

Kirchoff s power laws on the buses,

slack bus in the electrical power network;

properties of generator buses and loads in the electrical power network;

properties of transformers, line charging, capacitors, and condensors;

lower and upper bounds on voltage magnitudes and phase angles;

lower and upper bounds on active and reactive power; and

upper bounds on line apparent power.

The optimisation in (b) may be based on one of the following:

hot start model, wherein the information in (a) includes a known voltage magnitude at each bus; warm start model, wherein the information in (a) includes a desired target voltage magnitude at each bus; and

cold start model, wherein the information in (a) includes known voltage magnitude at each voltage-controlled generator bus only

The convex approximation may be used in an optimisation algorithm for one or more of: transmission planning, unit commitment, economic dispatch, demand response, transmission switching, vulnerability analysis, and placement of renewable resources or electrical power components in the electrical power network.

According to a second aspect, there is provided a computer program comprising computer-executable instructions to cause a computer to perform the method for alternating current (AC) power flow analysis in an electrical power network according to the first aspect. The computer-executable instructions may be stored in a computer- readable medium.

According to a third aspect, there is provided a computer system for alternating current (AC) power flow analysis in an electrical power network, the system comprising a processing device to perform the method according to the first aspect.

According to a fourth aspect, there is provided an electrical power network in which analysis of AC power flow is performed using the method-according to the first aspect. For example, results of the AC power flows analysis may be used to design and/or operate the electrical power network.

Brief Description of Drawings

Examples will now be described with reference to the accompanying drawings, in which:

Fig. 1 is a schematic diagram of an example system for AC power flow analysis; Fig. 2 is a flowchart of an example method for AC power flow analysis;

Fig. 3 is a detailed flowchart of the example method in Fig. 2; Fig. 4(a) and Fig. 4(b) are plots of the contour of (a) active power and (b) reactive power equations, respectively;

Fig. 5(a) is a graph of a piecewise linear approximation of cosine term(s) defining AC power flows;

Fig. 5(b) is an example algorithm for generating a piecewise linear approximation of cosine term(s) defining AC power flows;

Fig. 6(a) and Fig. 6(b) are plots of reactive power flow correlation for the LPAC Model on (a) IEEEddl 7m and (b) MP300 respectively;

Fig. 7(a) and Fig. 7(b) are plots of voltage magnitude correlation for the LPAC Model on (a) IEEEddl 7m and (b) MP300 respectively;

Fig. 8(a) is a plot of second-order Taylor approximation of cosine terms defining AC power flows;

Fig. 8(b) is a plot of second-order Taylor approximation of sine terms defining AC power flows;

Fig. 8(c) is a plot of linear approximation of voltage square terms defining AC power flows; and

Fig. 9 is a schematic diagram of an example structure of a processing device capable of AC power flow analysis. Nomenclature

Real numbers are denoted by lowercase letters and complex numbers by uppercase letters with a tilde above. A complex number V is represented as ν + ϊθ in rectangular form and \ ¥ \ ΖΘ ^' in polar form. The following letters are used for common quantities in power systems: Voltage V = v + ΐθ , current I , power S = p + iq , admittance Y = g + ib , and impedance Z = r + ix . Values with one subscript (e.g. S„ ) pertain to buses, while values with two subscripts (e.g. S _nm ) pertain to lines.

The following symbols are used throughout the disclosure.

/ Alternating current (AC)

ν = _{ν +} ιθ AC voltage AC power

Line impedance

Line admittance

Y-Bus element Line charge Bus shunt

Transformer tap ratio

Polar form of AC voltage

AC Power at bus n

AC Power on a line from n to m

Power network

Set of buses in a power network

Set of lines in a power network

Set of voltage controlled buses

Slack bus

Hot-Start voltage magnitude

Target voltage magnitude

Voltage magnitude change

Absolute difference

Percent difference

Approximation of x

Upper bound of x

Lower bound of x

Detailed Description

Fig. 1 shows an example system 100 that includes a processing device 110 capable of performing AC flow analysis for an electrical power network. In general, a power network is composed of several types of components such as buses, lines, generators and loads. The power network may be interpreted as a graph <N, E) where the set of buses N represent the nodes and the set of lines E represent the edges. For AC power flow studies: A subset of generators may be represented as G N and the slack bus s e G .

Every bus n e N in the network has two properties, a voltage N„ = v„ + \.9 _n and a power S„ = p _n + iq _n , both of which are represented as complex numbers due to the ossilating nature of current and voltage.

I V„ I may be used to denote the voltage magnitude /„ ² + Θ in the present disclosure.

Each line (n, m) E has an admittance Y _nm = g _nm + ib , also a complex number.

The above network values are generally connected by two fundamental physical laws, Kirchhoffs Current Law (KCL) and Ohm's Law. In the example in Fig. 1 , the electrical power network PN comprises four buses 120 (buses 1 to 4) and five transmission lines 130 (lines 1 to 5) connecting the buses 120. Bus 1 and Bus 4 are each connected to a generator 130. Three types of buses are shown, in which:

Bus 1 is known as a slack bus, which is an arbitrary bus in the network that has a generator and with known voltage magnitude and voltage phase.

Buses 2 and 3 are each known as a load bus, which is a bus that is not connected to a generator and with unknown voltage magnitude and voltage angle.

Bus 4 is a "generator" or voltage-controlled bus, which is a bus that has a generator and with known voltage magnitude.

Line 1 connects bus 1 to bus 2; line 2 connects bus 1 to bus 3; line 3 connects bus 1 to bus 4; line 4 connects bus 2 to bus 3; and line 5 connects bus 3 to bus 4. Although a four-bus, five-line power network is shown, it will be appreciated that this example can be extended to any arbitrary network defined by:

PN = (N,L,G,s) , where N is the set of buses, L is the set of lines (used interchangebly with E throughout the disclosure). G is the set of voltage-controlled generators, and .

slack bus. Example AC Power Flow Analysis Method

An example method for AC power flow analysis in the electrical power network is shown in Fig. 2. In general, the example method 200 includes the following steps performed by the processing device 1 10: At block 210, the processing device 1 10 determines a convex approximation of

AC power flows based on information relating to busses and transmission lines in an electrical power network. The convex approximation of AC power flows includes convex approximation of nonlinear cosine terms associated with active power components and reactive power components of the AC power flows.

At block 220, the processing device 1 10 optimises a convex objective function associated with the electrical power network using the convex approximation of ' the AC power flows. Equations defining the AC power flows are generally a system of non-convex, nonlinear equalities which are NP-hard (i.e. Non-deterministic, Polynomial time hard) to solve and extremely challenging computationally in general. Such non-convex models that are not guaranteed to converge (especially outside of operating conditions). According to the example method in Fig. 2, convex approximation of AC power flows is determined and used ίη the subsequent optimisation. As such, optimisation based on the convex approximation may be performed more accurately and efficiently, such as in low polynomial time. Further, since a convex model is used, discrete optimization ^" technology may be used to solve decision support problems in power systems more efficiently. This leads to more accurate approximation of AC power flows, as well as more efficient and cost-effective electrical power networks. As shown in more detail in the flowchart 300 in Fig. 3, the convex approximation at block 210 may be one of the following. Linear programming approximation of AC power flows (see block 212 in Fig.

3). This model ("LPAC model") includes linear approximation of cosine terms associated with the active power components and reactive power components. In one example, an outer approximation of the cosine terms is used. Convex quadratic programming approximation of AC power flows (see block

214 in Fig. 3). This model ("QPAC model") includes a second-order series approximation of cosine terms associated with the active power components and reactive power components. In one example, second-order Taylor approximation is used to approximate the cosine terms, but it should be > understood that other approximation techniques may be used, such as the convex outer approximation of LPAC model.

The convex approximation of AC power flows at block 210 may further include convex approximation of sine terms, such as using outer approximation or second-order Taylor approximation.

According to at least one example in the present disclosure, the LPAC and QPAC models may have one or more of the following properties:

1. reasonable accuracy both inside and outside normal operating conditions;

2. reasonable computational efficiency and scalability;

3. the ability to reason about voltage magnitudes and reactive power which become critical outside normal operating conditions;

4. the ability to be integrated in general purpose discrete optimization solvers, in particular Mixed-Integer Programming (MIP) or Mixed-Integer Nonlinear

Programming (MINLP) solvers (e.g. CPLEX, Gurobi, and Bo min) and their hybridizations with Constraint Programming (CP) and Large Neighbourhood Search (LNS).

Optimisation at block 220 may then be performed based on a set of nonlinear constraints that includes convex approximation of cosine terms associated with the active power components and reactive power components. Suitable applications of the optimisation include but not limited to: optimal power flow, node pricing market calculations, transmission switching, distribution network configuration, capacitor placement, expansion planning, vulnerability analysis, and power system restoration.

Referring to Fig. 3 again, some example objective functions discussed in the present disclosure are as follows (it should be understood that either the LP AC or QPAC model may be used in the optimisation): In an AC power flow application (see block 222 in Fig. 3), the optimisation is to optimise the convex approximation of the AC power flows, or more specifically convex approximation of the cosine terms associated with the active and reactive power components. Examples are presented in Models 1 , 2 and 3 below, in which linear programming approximation of AC power flows is used. It should be understood that the examples may also be adapted to the case of convex quadratic approximation.

In a power restoration application (see; block 224 in Fig. 3), the optimisation is to maximise load(s) in the electrical power network. An example is presented in Model 4 below, in which linear programming approximation of AC power flows is used. It should be understood that the example may also be adapted to the case of convex quadratic programming approximation.

In a capacitor placement application (see block 226 in Fig. 3), the optimisation is to minimise the number of capacitors place in the electrical power network. Examples are presented in Model 5 (linear programming) and Model 10 (convex quadratic programming) below.

In an AC optimal power flow (OPF) application (see block 228 in Fig. 3), the optimisation is to minimise generator cost, i.e. to find the cheapest way to generate power in order to satisfy customers' demand given some cost functions of generators. An example is presented in Model 9 below, in which convex quadratic programming approximation is used. It should be understood that the example may also be adapted to the case of linear programming approximation.

The optimisation may be based on hot, warm or cold start models, as follows. It should be understood that either the LP AC or QPAC model may be used in the following.

In the hot start model, the optimisation is based on known voltage magnitudes. An example is shown in Model 1 using linear programming approximation, but this may be similarly used in the context of convex quadratic programming approximation.

In the warm start model, the optimisation is based on desired target voltage magnitudes. An example is shown in Model 2 using linear programming approximation, but this may be similarly used in the context of convex quadratic programming approximation.

In the cold start model, no reasonable voltage magnitudes are known and the optimisation is based on voltage controlled generator values. An example is shown in Model 3 using linear programming approximation, but this may be similarly used in the context of convex quadratic programming approximation.

Examples will now be described with reference to Figs. 4 to 9. Section 1 provides an introduction to AC power flow equations, Section 2 provides example implementations of the LP AC model and Section 3 provides example implementations of the QPAC model.

Section 1 - AC Power Flows

In steady state, AC power for bus n is given by

Sn = y _n Vn Y _nm -v _n v „ _m , ( l ) m

This equation is not symmetric. From the perspective of bus n , the power flow on a line to bus n is

V n V n Y nm V ^' n V ^' m Y nm

while, from the perspective of bus m , it is

In general, the AC power flow from bus n to bus m is not the same as the AC power flow from bus m to bus n, i.e. 5 nm -f- S mn · To model AC power flows, generators in the power system benchmarks are voltage- controlled. This means that every generator n e G has a predetermined voltage ma nitude \v \ , which fixes the voltage magnitude decision variable \ V„\ , i.e., (a) Traditional Representation

The AC power flow definition is generally expanded in terms of real numbers only. Complex numbers may be represented in rectangular or polar coordinates, i.e.,

V = ν + ϊθ -\ ν \ Ζ.Θ" . Because power networks generally operate near a nominal voltage (i.e., V» « 1.0Z0 ), the voltages may be represented in polar coordinates and the remaining terms (power and admittance) in rectangular coordinates.

By representing power in rectangular form, the real ( p _n ) and imaginary ( q _n ) terms become: A _™ =∑l Vn i ² g _nm -\ v. II v _m I (g _nm cos(0 _n '-e _m yrb _nm &ιη ;-ϋ„ ^' ) q _nm = Ϋτ\ν» I ² _m -\ v _n II v _m I ( _{gnm S} [n(e-e, b, _m

The Y-Bus Matrix: The formulation can be simplified turther by using a Y-B s Matrix, i.e., a precomputed lookup table that allows the power flow at each bus to be written as a summation of n terms instead a summation of 2(w-l) terms. Observe that, in the power flow equations (1), the first term V„V„Y _nm is a special case of the second term -V„V _m Y„ _m with -V _m = V„. In general, we can eliminate this special case by:

1. extending the summation to include n terms, i.e., becomes∑ _m

2. defining the Y-Bus admittance Y„ _m - g _n ^y _m + ib _n ^} _m as

Y Y

~h

Y nn -Y _n

Given the Y-Bus, the power flow equations (1) can be rewritten as a single summation

giving us the popular formulation of active and reactive power components:

p„ ==2 V ₉ II V. I (g os{e;^W _nm sin(¾H9;)) (3)

9. cos(¾-0 » (4)

(b) An Alternate Representation The Y-Bus formulation is concise but makes it difficult to reason about the power flow equations. This paper uses the more explicit equations which can be presented as bus and line equations as follows:

Λ =∑Α», (5) m

1„ ⁼ ∑?™ (6) Pnm =1 V* f g, _m - \ V _n II V _m I g _nm cos(0: - ø;)- 1 V. || V _m \ b, _m sin(0; ) (7)

<?„ _m = - 1 v» I ² ^ + 1 v _n II F _m 1 6„ _m cos(0; -&„ \ v„ \\ v _m \ _{gnm s-} n(0; - 6>; ) (8)

Once again, Equations (7) and (8) are asymmetric and p _nm and q _nm are defined for each (n, m) e E . Also, g and 6 represent the line admittance values Y = g + ib . As will be demonstrated using examples below, the polar representation of voltage is useful for building approximations around the nominal operating point.

(c) Extensions for Practical Power Networks

In the above derivation, each line is a conductor with an impedance Z . The formulation can be extended to line charging and other components such as transformers and bus shunts, which are present in nearly all AC system benchmarks. Example model for these extensions in the Y-Bus formulation are shown below for simplicity.

(i) Line Charging

A line connecting buses n and m may have a predefined line charge

Y = g ^c + ib ^c . Linearizations of AC model typically assume that a line charge is evenly distributed across the line and hence it is resonable to assign equal portions of its charge to both sides of the line. This is incorporated in the Y-Bus matrix as follows:

~ b' ~ b ~c

Y ^' nn Y tm " ^* nm ! 2, (ii) Transformers

A transformer connecting bus n to bus m can be modeled as a line with modifications to the Y-Bus matrix. The properties of the transformer are captured by a complex number T _nm =| T \ Zs° , where | Γ | is ¹ the tap ratio from n to m and s" is the phase, shift. It is worth noting that the direction of a transformer-line is very important to model the tap ratio and phase shift properly. A transformer is modeled in the Y-Bus matrix as follows:

Y mn Y mn I Ύ nm _*

If a line charge exists, it must be applied before the transformer calculation, i.e., Ynm + (Y, nm + Ynm I 2)1 I Tnm

(iii) Bus Shunts

A bus n may have a shunt element which is modeled as a fixed admittance to ground with a value of Y = g + ib ^* . In the Y-Bus matrix, we have

Unlike line charging, this extension is not affected by transformers, since it applies to a bus and not a line.

(d) Linearized DC Power Flow

The DC power flow model is a common response to the computational challenges of the AC power flow equations. Many variants of the Linearized DC (LDC) model exist. For brevity, we only review the simplest and most popular variant of the LDC, which is derived from the AC equations through a series of approximations justified by operational considerations under normal operating conditions. In particular, the LDC assumes that (1) the susceptance is large relative to the impedance | g |< | 6 | ; (2) the phase angle difference e _n ° -e _m ' \s small enough to ensure sin(# ^° - 0 ^° ,) ~ θ _η " -ff _m and cos(#,° -θ _η " ) « 1.0 ; and (3) the voltage magnitudes \ V \ are close to 1.0 and do not vary significantly. Under these assumptions, Equations (7) and (8) reduce to

From a computational standpoint, the DC power flow model may be much more appealing than the AC model: It forms a system of linear equations that admit reliable algorithms. These linear equations can also be embedded into MIP solvers. Under normal operating conditions and with some adjustment for line losses, the DC model produces a reasonably accurate approximation of the AC power flow equations for active power. Unfortunately, recent results have demonstrated that the inaccuracies of the DC power flow can be significant. Section 2 - LPAC Model

This section presents linear-programming approximations of the AC power flow equations. To understand the approximations, it is important to distinguish between hot-start and cold-start contexts. In hot-start contexts, a solved AC base-point solution is available and hence the model has at its disposal additional information such as voltage magnitudes. In cold start contexts, no such solved AC base-point solution is available and it can be "maddeningly difficult" to obtain one by simulation of the network.

Hot-start models are well-suited for applications in which the network topology is relatively stable, e.g., in LMP-base market calculations, optimal line switching, distribution configuration, and real-time security constrained economic dispatch. Cold- start models are used when no operational network is available, e.g., in long-term planning studies. We also introduce the concept of warm-start contexts, in which the model has at its disposal target voltages (e.g., from normal operating conditions) but an actual solution may not exist for these targets. Warm-start models are particularly useful for power restoration applications in which the goal is to return to normal operating conditions as quickly as possible.

This section presents hot-start, warm-start, and cold-start model in stepwise refinements. It also discusses how models can be generalized to include generation and load shedding, remove the slack bus, impose constraints on voltages and reactive power, and capacity constraints on the lines, all which are fundamental for many applications. In one or more embodiments, the LP AC models have the potential to broaden the success of the traditional LDC model into new application areas and to bring increased accuracy and reliability to current LDC applications. There are many opportunities for further study, including the application of the LPAC models to a number of application areas. From an analysis standpoint, it would be interesting to compare the LPAC models with an AC solver using a "distributed slack bus'". Such an AC solver models the real power systems more accurately and provides a better basis for comparison, since the LPAC models are easily extended to flexible load and generation at all buses.

One example of the LPAC model has been experimentally evaluated over a number of standard benchmarks under normal operating conditions and under contingencies of various sizes. Experimental results shows strong correlations between the method and solutions to the AC power equations for active and reactive power, phase angles, and voltage magnitudes. Moreover, the method may be integrated in mixed integer programming (MIP) models for applications reasoning about reactive power (e.g., capacitor placement) or topological changes (e.g., transmission planning and power restoration).

In one example, the method captures reactive power accurately in a linear model, which leads increased accuracy of voltage magnitudes, reactive power, and line loading. It does this while being fast (low polynomial time). Existing linear models do not capture reactive power accurately because they often do not capture reactive power at all. Further, nonlinear models are not guaranteed to converge, especially outside operating conditions.

(a) AC Power Flow Behavior

Before presenting the models, it is useful to review the behavior of AC power flows, which is the main driver in the derivation. The high-level behavior of power systems is often characterized by two rules of thumb in the literature:

(1) Phase angles are the primary factor in determining the flow active power;

(2) Differences in voltage magnitude are the primary factor in determining the fl o w o f reactive power.

This section examines these experimentally to guide our linear-programming approximation of the AC-flow equations in a cold-start context. The experiments make two basic assumptions:

(1) In the per unit system, voltages do not vary far from 1.0 and Ρ ε [-π / 36,-π /36] ;

(2) The magnitude of a line conductance is much smaller than the magnitude of the susceptance, i.e., | g b \ .

We can then explore the bounds of the power flow equations (7) and (8), when the voltages are in the following bounds: | V„ \= 1.0, | V _m \e (l ,2,0.8), and θ _η ^' - 9 _m " e -π / 6,π / 6) . In some applications, these are generous bounds that exceed normal operating conditions of all buses in the standard IEEE power system benchmarks: The motivation here is also to see how active and reactive power behave outside normal operating conditions.

Fig. 4(a) presents the contour of the (a) active power and (b) reactive power equations for a line (n,m) under these assumptions when = 0.2 -/1. The contour lines indicate significant changes in power flow. Consider first the active power plot in Fig. 4(a). For a fixed voltage, varying the phase angle difference induces significant changes in active power as many lines are crossed. In contrast, for a fixed phase angle difference, varying the voltage has limited impact on the active power, since few lines are crossed. Hence, Fig. 4(a) indicates that phase angle differences are the primary factor of active power flow while voltage differences have only a small effect.

The situation is quite different for reactive power in Fig. 4(b). For a fixed voltage, varying the phase angle difference induces some significant changes in reactive power as around four lines can be crossed. But, if the phase angle difference is fixed, varying voltage induces even more significant changes in _\ reactive power since as many as seven lines may now be crossed. Hence, changes in voltages are the primary factor of reactive power flows but the phase angle differences also have a significant influence.

(b) Hot-Start Linear-Programming Approximation

The linear-programming approximation of the AC Power flow equations in a hot-start context is based on three ideas:

1. It uses the voltage magnitude | V„ | from the AC base-point solution at bus n ;

2. It approximates sin(x) by x ;

3. It uses a piecewise-linear approximation of the cosine.

The piecewise-linear approximation produces a set of inequalities. If cos(0^ -9 _m ^' ) denotes the piecewise-linear approximation of cos(<¾ - # ^° ) , then the linear- programming approximation solves the following constraints: v _* II v I *.««(<¾ -<¾;)- 1 vl it i I b _nn {& _n -e _m ) (10) nm + \ v"„ [I v ^h _m \ h v \\ v \ g _n M - (Π) The piecewise linear approximation is computed for a domain (/, h) and a number of desired segments 5 . A domain (-/r / 2,/r / 2) is reasonable although, in practice, θ _η - 0 _m ^" is typically very small and a tighter domain may be chosen. Fig. 5(a) illustrates an example approximation approach using seven linear inequalities. The dark black line (510) shows the cosine function, the dashed lines (520, 522, 524, 526, 528, 530, 532) are the linear inequality constraints, and the shaded area (540) is the feasible region of the linear system formed by those constraints. The inequalities are obtained from tangents to points of the function. Specifically, for a point x , the tangent is 0 =— sin(x)(¾' - x) - (/ - cos( )) and, within the domains of {-π / 2, π 12) , the following inequality holds:

cos(x)≤ - sin(x)(x' - x) - (y - COS(JC)) . Fig. 5(b) provides an example algorithm to generate ,9 inequalities evenly placed within (l, h) such as (-π / 2, π / 2) in Fig. 4(a). In the algorithm, x is a decision variable used as an arg ⁰ ument of the cosine function and x—os is a decision variable capturing the approximate value of cos(x) . Advantageously, this approximation captures the cosine contribution to reactive power. However, the applicability of the model might be limited since, for example, placing tight bounds on reactive power can easily make the model infeasible. This is because reactive power is greatly effected by changes in voltage magnitudes as we now discuss.

Model 1: Hot-Start Linear Programming Approximation

Inputs:

PN = (N,L ,G, s) - the power network

- voltage magnitudes from an AC base-point solution cs - cosine approximation segment count

Variables: θ° €(-00,00) phase angle on bus n (radians)

cosnn, e (0,1) Approximation of cos(0° - ( _m ) Maximize:

∑. , , C .f nm (Ml . l)

(n.m)e/.

Subject to:

θ = 0 (Ml .2)

ρίή v\ I ² g _n ,„H II ν I (g _nm c s„ _m + 6 _Mm (¾ - ^(ML5)

?! I ² ^ II I -e _m °)-b _nm ∞s _m ,) ( ^ML6 >

PWL<C05> (cos _nm ,(^ - ^), -¾- / 3,^ / 3,c5) ( ^{M1 J} ) (c) Warm-Start Linear-Programming Approximation

This section derives the warm-start LPAC model, i.e., a Linear-Programming model of the AC power flow equations for the warm-start context. The warm-start context assumes that some target voltages | V | are available for all buses except voltage- controlled generators whose voltage magnitudes V. ^g are known. In some applications, the network must operate close (e.g., ±0.1 Volts p.u.) to these target voltages, since otherwise the hardware may be damaged or voltages may collapse. The warm-start LPAC model is based on two key ideas:

1. The active power approximation is the same as in the hot-start model, with the target voltages replacing the voltages in the base-point solution;

2. The reactive power approximation reasons about voltage magnitudes, since changes in voltages are the primary factor of reactive power flows.

To derive the reactive power approximation in the warm-start LPAC model, let φ be the difference between the target voltage and the true value, i.e., \V\=\V \+φ.

Substituting in Equation (8), we obtain

^=-(l^| ² +2|F' _w |^ ₊ ^)6„ _m - ν^\ \ + \ν'*\Φ _η +\ν'»\Φ,,+ΦΑ )(g _nm s (0 - Θ ) - b, _m cos : - ))

(12)

Dividing the terms into h t-start and cold-start part gives

where q _nm is Equation (8) with | V |=| V | and q _m captures the remaining terms, i.e.,

ql ⁼ -(21 v I φ„ + Φ )b _nm -(I ν»\Φ„ + \ν>»\Φ„+Φ _η Φ _η , ){g _nm sin(¾ ^" - ff _m ) - 6„ _m costfr - έΓ ))

(14)

This equation is equivalent to Equation (8), which is now linearized to obtain the LPAC model.

The q _n ' _m part has target voltages and may thus be approximated like q _n ^h _m . The q^ _m is more challenging as it contains nonlinear and non-convex terms such as φ _η φ _η cos(6 _n ^' -#„)· We approximate q _m using the linear terms of the Taylor series of

< _l L at θ ^' -θ ^' =0 to obtain

& = -(21 V„ I ^„„, +(| V'„ \φ„+\ νΙ I (15) or, equivalently,

41 ⁼ -I I - rf.) - ⁽ I v"' I - 1 v»\)KA (16)

An example linear program for this formulation is presented in Model 2.

Model 2: Warm-Start Linear Programming Approximation

Inputs:

PN = (N, L, G, s) - the power network \ V target voltage magnitudes

cs - cosine approximation segment count

Variables:

θ„' e (-∞,∞) phase angle on bus n (radians)

Φ„ζ {- \ ν· \,∞) - voltage change on bus n (Volts

cosnm e (0, 1) approximation of cos(# _n ^' - #„°,)

Maximize:

∑ (M2.1 )

(n,m)e/. COSnm

Subject to:

Θ = Ο,Φ, = Ο (M2.2) φ, = 0 V/ e G (M2.3)

(M2.4)

<?I _m =H ft I ² II ft I (M2.7)

(i 0; -ei) -b„ _m ∞s„ _m )

(M2.8) *1 = - 1 ft I - A, ⁾ - ⁽ I ft I - 1 ft< ΙΜ ,

PWL (COS) (ws„, , (# - ff _m ), -π 13 , π 13 , cs) (M2.9)

The inputs to the model are:

(1) A power network PN = (N, L,G,s) , where ^" N is the set of buses, L is set of lines, G is the set of voltage-controlled generators, s is the slack bus;

(2) the target voltages | V | for the buses, and

(3) the number of segments cs for approximating the cosine function.

The objective function (M2.1) maximizes the cosine approximation to make it as close as possible to the true cosine. The constraints are:

Constraints (M2.2) model the slack bus, which has fixed voltage and phase angle.

Constraints (M2.3) capture the voltage-controlled generators which, by definition, do not vary from their voltage target | V | .

Constraints (M2.4) and (M2.5) model CL on the buses, as well as the effects of voltage change presented in Equation (16). Like in AC power flow models, the KCL constraints are not enforced on the slack bus for both active and reactive power and on voltage-controlled generators for reactive power.

Constraints (M2.6) and (M2.7) capture the approximate line flows from Equations (10) and (11).

Constraints (M2.8) model the effects of voltage change presented in Equation

(16).

Constraints (M2.9) define a system of inequalities capturing the piecewise-linear approximation of the cosine terms in the domain {-π / 3,π 13) using cs line segments for each line in the power network.

(d) Cold-Start Linear-Programming Approximation

We now conclude by presenting the cold-start LP AC model. In a cold-start context, no target voltages are available and voltage magnitudes are approximated by 1.0, except for voltage-controlled generators whose voltages are given by | V„ | (n e G) . The cold- start LPAC model is then derived from the warm-start LP AC model by fixing | V, |= 1 for all i e N . Equation (16) then reduces to

- 07)

Model 3 sets out the cold-start LPAC model, which is very close to the warm-start model. Note that Constraints (M3.3) use ^ to fix the voltage magnitudes of generators.

Model 3: Cold-Start Linear Programming Approximation

Inputs: PN = (N,L,G,s) - the power network

cs cosine approximation segment count

Variables:

Θ _Η ' e (-οο,οο) - phase angle on bus n (radians)

Φ„≡{-\ν' Ι,οο) - voltage change on bus n (Volts p.u.)

cosnm e(0,l) - approximation of cos(# - 9 _m ° )

Maximize:

Subject to:

Θ;=Ο,Φ,=Ο (M3.2)

φ, =| V] 1-1.0 V eG (M3.3)

^ ⁼ Σ _β ¾+ί1 ^v " ^{e Ar} «≠^ n^G V(«,m>,(m,«>eZ (M3.5) » ⁼ ^ _™ -^« _m cos _™ + (M3.6)

6„ _m (0„ ^' - # _m )

^-g^ (¾ ^° - ¾ ) - (M3.7)

6 _nff , cos _™

(M3.8)

(e) Extensions to the LPAC Model

The LPAC model can be used to solve the AC power flow equations approximately in a variety of contexts: Hot-start and cold-start contexts, as well as situations in which voltage targets are available. This section reviews how to generalize the LPAC model for applications in disaster management, reactive voltage support, and vulnerability analysis.

(i) Generators

The LPAC Model can easily be generalized to include ranges for generators:

Simply remove the generator from G and place operating limits on the p and q variables for ^' that bus. In that formulation, voltage-controlled generators can also be accommodated by fixing φ _η to zero at bus n . (ii) Removing the Slack Bus

By necessity, AC solvers generally use a slack bus to ensure the flow balance in the network when the total power consumption is not known a priori (e.g., due to line losses). As a consequence, the LPAC Model also uses a slack bus so that the AC and DC models can be accurately compared in our experimental results. However, it is important to emphasize that the LPAC model does not need a slack bus and the only reason to include a slack bus in this model is to allow for meaningful comparisons between the LPAC and AC models. As discussed above, the LPAC model can easily include a range for each generator, thus removing the need for a slack bus.

(iii) Load Shedding

For applications in power restoration, the LPAC model can also integrate load shedding: Simply transform the loads into decision variables with an upper bound and maximize the load served. The cosine maximization should also be included in the objective but with a smaller weight. Experimental results on power restoration will be presented later.

(iv) Modeling Additional Constraints

In practice, feasibility constraints may exist on the acceptable voltage range, the reactive injection of a generator, or line flow .capacities. Because Model 1 is a linear program, it can incorporate such constraints. For instance, constraint

\ ν \≤\ ν _η ' \ +φ _η Vrc e N

ensures that voltages are above a certain limit \ V \ , constraint

limits the maximum reactive injection bounds at bus n to q _n . Finally, let | S _nm \ be the maximum apparent power on a line from bus n to bus m . Then, constraint ensures that line flows are feasible in the LPAC model. The quadratic functions can be approximated by piecewise-linear constrains. The auxiliary variables need not appear in the objective as they are constrained from above by | S _nm \ .

Accuracy Analysis of LPAC Model

This section evaluates the accuracy of the LPAC model which was extended to include line charging, bus shunts, and transformers, as discussed above. It includes (a) a detailed analysis of the model accuracy and (b) an investigation of additional approximations. ■

The experiments were performed on nine traditional power-system benchmarks which come from the IEEE test systems and Matpower. The AC power flow equations were solved with a Newton-Raphson solver which was validated using Matpower. The LPAC models use 20 line segments in the cosine approximation and all of the models solved in less than 1 second. The results also include a modified version of the IEEEddl 7 benchmark, called IEEEddl7m. The original IEEEddl 7 has the slack bus connected to the network by a transformer with | T |= 1.05 . The non-linear behavior of transformers induces some loss of accuracy and, because this error occurs at the slack bus in IEEEddl 7, it affects all buses in the network. IEEEddl 7m resolves this issue by setting I |= 1.00 and the slack bus voltage to 1.05 . This equivalent formulation is significantly better for the LPAC model.

(a) LPAC Model

This section reports empirical evaluations of the LDC and LPAC models in cold-start and hot-start contexts. It reports aggregate statistics for active power (Table 1), bus phase angles (Table 2), reactive power (Table 3), and voltage magnitudes (Table 4). Data for the LDC model is necessarily omitted from Tables 3 and 4 as reactive power and voltages are not captured by that model. In each table, two aggregate values are presented: Correlation (corr) and absolute error ( Δ). The units of the absolute error are presented in the headings. Both average ( μ ) and worst-case ( max ) values are presented. The worst case can often be misleading: For example a very large value may actually be a very small relative quantity. For this reason, the tables show the relative error ( δ ) of the value selected by the max operator using the arg - max operator. The relative error is a percentage and is unit-less.

Table 1 indicates uniform improvements in active power flows, especially in the largest benchmarks IEEE1 18, IEEEddl 7, and MP300. Large errors are not uncommon for the linearized DC model on large benchmarks and are primarily caused by a lack of line losses. Due to its asymmetrical power flow equations and the cosine approximation, the LPAC model captures line losses.

Table 1: Accuracy of the LPAC Model: Active Power Flows.

Table 2 presents the aggregate statistics on bus phase angles. These results show significant improvements in accuracy especially on larger benchmarks. The correlations are somewhat lower than active power, but phase angles are quite challenging from a numerical accuracy standpoint.

Table 2: Accuracy of the LPAC Model; Phase Angles.

Benchmark Phase Angle (rad)

Corr μ(Α) max(A) £(arg max(A))

The LDC Model

ieeel 4 0.9993 0.02487 0.04258 15.22

mp24 0.9997 0.01334 0.02037 15.23

ieee30 0.9981 0.02831 0.04733 1 6.45

mp30 0.98 0.005658 0.01607 30.27

mp39 0.9951 0.0283 0.05813 85.56

ieee57 0.9898 0.02244 0.05958 24.1

ieeel 18 0.9904 0.03452 0.09026 88.41

ieeeddl 7 0.9892 0.1 15 0.1395 16.09

ieeeddl7m 0.992 0.0461 0.06924 41.88

mp300 0.9752 0.3103 0.4244 975.7

The LI PAC-Cold Start Model

ieeel 4 0.9971 0.004525 0.01241 5

mp24 0.9999 0.003539 0.008947 6.922

ieee30 0.9965 0.007268 0.02413 8.386

mp30 0.9782 0.006236 0.01804 33.99

mp39 0.9989 0.006268 0.02314 34.06

ieee57 0.9894 0.0179 0.05467 22.1 1

ieeel 18 0.9994 0.003225 0.01354 9.633

ieeeddl7 0.9981 0.03648 0.05165 5.958

ieeeddl7m 0.999 0.007207 0.02682 4.522

mp300 0.9984 0.01458 0.08086 38.49

The LPAC-Hot Start Model

ieeel 4 1 0.001448 0.001829 0.6914 mp24 1 0.001337 0.002203 2.156

ieee30 1 0.002345 0.002819 0.9629

mp30 0.9998 0.001298 0.001774 4.775

mp39 0.9999 0.005315 0.006241 4.273

ieee57 1 0.00271 1 0.00357 1.776

ieeel l 8 0.9999 0.005958 0.008366 2.526

ieeeddl7 0.9999 0.01492 0.01719 2.419

ieeeddl 7m 0.9999 0.008443 0.01059 2.33

mp300 0.9997 0.03842 0.04502 18.51 '

Table 3 presents the aggregate statistics on line reactive power flows. They indicate that reactive power flows are generally accurate and highly precise in hot-start contexts. To highlight the model accuracy in cold-start contexts, the reactive flow correlation for the two worst benchmarks, IEEEddl 7m and MP300, is presented in Fig. 6.

Table 3: Accuracy of the LPAC Model: Reactive Power Flows.

Benchmark Reactive Power (MVar)

Corr μ(Α) max(A) £(arg max(A))

The L] PAC-Cold Start Model

ieeel4 0.9895 0.8689 3.167 43.89 mp24 0.9992 1.505 5.245 9.309 ^' ieee30 0.9975 0.3455 1.607 7.62 mp30 0.9991 0,3135 0.8925 3.886 mp39 0.9971 4.03 15.75 18.98 ieee57 0.9995 0.3853 1.46 5.67 ieeel l 8 0.9992 0.6326 6.109 6.808 ieeeddl7 0.9791 3.985 48.37 40.34 ieeeddl7m 0.9927 2.409 33.96 12.28 mp300 0.9943 3.584 162 45.05

The LPAC-Hot Star t Model

ieeel4 0.999 0.3313 1.027 66.27 mp24 0.9995 1.012 4.356 7.73 ieee30 0.9972 0.3196 2.139 26.26 mp30 0.9999 0.1152 0.3807 8.448 mp39 0.9974 3.547 23.51 24.15 ieee57 0.9994 0.3957 1.96 10.92 ieeel l8 0.9997 0.3946 4.168 5.712 ieeedd 17 0.9936 2.325 30.59 25.51 ieeeddl 7m 0.993 2.235 39.08 14.14 mp300 0.9991 2.198 24.63 5.513 Table 4 presents the aggregate statistics on bus voltage magnitudes. These results indicate that voltage magnitudes are very accurate on small benchmarks, but the accuracy reduces with the size of the network. The warm-start context brings a significant increase in accuracy in larger benchmarks. To illustrate the quality of these solutions in cold-start contexts, the voltage magnitude correlation for the two worst benchmarks, i.e., IEEEddl 7m and MP300, is presented in Fig. 7(a) and Fig. 7(b).

The increase in voltage errors is related to the distance from a load point to the nearest generator. The linearized voltage model incurs some small error on each line. As the voltage changes over many lines, these small errors accumulate. By comparing the percentage of voltage-controlled generator buses in each benchmark | G | / 1 N | (Table

5) to accuracy in Table 4, the IEEE57 and IEEEddl7 benchmarks indicate that that a low percentage is a reasonable indicator of the voltage accuracy in the cold-start context.

Table 4: Accuracy of the LPAC Model: Voltage Magnitudes.

Voltage Magnitude (Volts p.u.)

Benchmark

Corr Δ) max(A) <5(arg max(A))

The L] PAC-Cold Start Model

ieeel4 0.9824 0.003365 0.01328 1.258 mp24 0.9983 0.000676 0.003244 0.3362 ieee30 0.9912 0.00246 0.01 126 1.127 mp30 0.9884 0.002186 0.009453 0.9723 mp39 0.9991 0.0007851 0.002281 0.2157 ieee57 0.9723 0.01044 0.03366 3.601 ieeel 18 0.999 0.000694 0.0045 0.4657

ieeedd-7 0.9649 0.01369 0.03339 3.418 ieeeddl 7m 0.9813 0.006405 0.01573 1.654 mp300 0.9951 0.002207 0.01385 1.5

The LPAC-Hot Star t Model

ieeel 4 0.9998 0.0005571 0.001207 0.1 143 mp24 0.9997 0.0004967 0.002024 0.2097 ieee30 0.9994 0.001409 0.002415 0.2407 mp30 1 0.0003685 0.000669 0.06908 mp39 0.9984 0.001498 0.0034 0.338 ieee57 0.999 0.00194 0.004861 0.5055 ieeel 18 0.9999 0.0001885 0.001234 0.1273 ieeeddl 7 0.994 0.008863 0.01822 1.956 ieeeddl 7m 0.9874 0.007749 0.01545 1.592 mp300 0.9974 0.00224 0.01 181 1.279

Table 5: The Ratio of Voltage-Controlled Buses.

ieeel4 mp24 ieee30 mp30 mp39

35.7% 45.8% 20.0% 20.0% 30.8% ieee57 ieeel 18 ieeeddl7 mp300

12.3% 45.8% 7.4% 24.7%

(b) Alternative Linear Models

The formulation of the LP AC model explicitly removes two core assumptions of the traditional LDC model:

1. Although cos(#° - #° ) maybe very close to 1 , those small deviations are important.

2. Although the conductance contributes significantly to the phase angles and voltage magnitudes.

This section investigates three variants of the LP AC models that reintegrate some of the assumptions of the LDC model. The new models are: (1 ) the LPAC-C model where only the cosine approximation is used and g = 0 ; (2) the LPAC-G model where only the g value is used and cos(x) = 1 ; (3) the LPAC-CG model where cos(x) = 1 and g = .

Tables 6 and 7 present the cumulative absolute error between the proposed linear formulations and the true nonlinear solutions. Many metrics may be of interest but these results focus on line voltage drop V„ - V _m and bus power S _n . These were selected because they are robust, to errors which accumulate as power flows through the network. The results highlight two interesting points. First, all linear models tend to bring improvements over a traditional LDC model. Second, although integrating either the g value or the cosine term brings some small improvement independently, together they make significant improvements in accuracy. Additionally a comparison of Table 6 and Table 7 reveals that the benefits of the new linear models are more pronounced as the network increases.

Table 6: Accuracy Comparison of Various Linear Models (Pari I).

Table 7: Accuracy Comparison of Various Linear Models (Part II).

Model Cumulative Absolute Error

Power Restoration based on LPAC Model

After a significant disruption due to, say, a natural disaster, large sections of the power network need to be re-energized. To understand the effects of restoration actions, power engineers must simulate the network behavior under various courses of action. However, the network is far from its normal operating state, which makes it extremely challenging to solve the AC power flow equations. In fact, the task of finding an AC solution without a resonable starting point has been regarded as "maddeningly difficult". . The LPAC model studied here has the benefit of providing starting values for all the variables in the AC power flow problem, unlike the traditional LDC which only provides active power values. Furthermore, the LPAC model has the additional advantage of supporting bounds on reactive generation and voltage magnitudes and such constraints are critical for providing feasible solutions to the AC power flow. This section illustrates these benefits.

Before presenting the power-restoration model, it is important to mention the key aspect of this application. When the power system undergoes significant damages, load shedding must occur. The LDC and LPAC models must be embedded in a restoration model that maximizes the served load given operational constraints such as the generation limits. These load values indicate the maximum amount of power that can be dispatched while ensuring system stability. Model 4 presents a linear program based on the warm-start LPAC model which, given limits on active power generation p ^g and the desired active and reactive loads p' , q at each bus, determines the maximum amount of load that can be dispatched. The model assumes that the loads can be shed .continuously and that the active and reactive parts of the load should maintain the same power factor.

Model 4: A Linear Program for Maximizing Desired Load

Inputs:

p - maximum active injection for bus n

p„' - desired active load at bus n

q _n ' / - desired reactive load at bus n

Inputs from Model 2 (Warm-Start)

Variables:

p e ,ρ^) - active generation at bus n

q* e (-0O, oo) - reactive generation at bus n

l _n € (0, 1) - percentage of load served at bus n

Variables from Model 2 (Warm-Start) Maximize:

(M4.1 )

Subject to:

(M4.2)

(M4.3)

q„* = 0 V«€N \ G (M4.4)

(M4.5)

Constraints from Model 2 (Warm-Start)

The objective function (M4.1) maximizes the percentage of served load. Constraints (M4.2) and (M4.3) set the active and reactive injection at bus appropriately based on the decision variables for load shedding and generation dispatch. Constraint (M4.4) ensures that reactive generation only occurs at generator buses and Constraint (M4.5) now defines for generator buses as well.

Since it reasons about reactive power and voltage magnitudes, Model 4 can be further enhanced to impose bounds on these values. As we will show, such bounds are often critical to obtain high-quality solutions in power restoration contexts. If a reactive a ^g

generation bound ^y is supplied, this model can be extended by adding the constraint, ql≤ q Vn e N.

Voltage magnitude limits can also be incorporated. Given upper and lower voltage

^■ rp ^~ i \ p \

limits ^{1 1} and—■ , the constraint

\ ν \≤\ Λ + φ„≤\ ν \ Vn e N.

may be used to enforce bounds on voltage magnitudes. The experimental results study the benefits of the LPAC model, suitably enhanced to capture these extensions, for power restoration. They compare a variety of linear models including the LDC model, the LPAC model, and enhancements of the LPAC model with additional constraints on reactive power and voltage magnitudes.

Table 8: Power Restoration: Achieving AC Feasibility From Different Models. Scenario LDC LPAC LPAC-R LPAC-R-V

N-3 997 998 1000 1000

Λ 997 1000 1000 1000

N-5 944 957 974 1000

N-6 973 1000 999 1000

N-7 973 985 994 1000

N-^8 976 979 998 1000

N-9 839 940 990 1000

N-10 664 674 818 1000

N-l l 494 623 973 997

N-12 697 698 981 1000

N-13 996 996 1000 1000

N-14 933 933 1000 1000

N-15 936 936 989 1000

N-16 696 696 942 1000

N-17 350 350 640 1000

N-18 1000 1000 1000 1000

N- 9 798 800 937 1000

N-20 1000 1000 1000 1000

Table 8 studies the applicability of various linear power models for network restoration on the ΓΕΕΕ30 benchmark. 1000 line outage cases were randomly sampled from each of the N-3,N-4,N-5,... ,N-20 contingencies. Each contingency is solved with a linear power model (e.g., the LDC model or the LPAC model), whose solution is used as a starting point for the AC model. The performance metric is the number of cases where the AC solver converges, as a good linear model should yield a feasible generation dispatch with a good starting point for the AC solver. To understand the importance of various network constraints, four linear models are studied: the traditional LDC model; the LPAC model; the LPAC model with constraints on reactive generation (LPAC-R); and the LPAC with constraints on reactive generation and voltage limits (LPAC-R-V). The number of solved models for each of the contingency classes is presented in Table 8. The results indicate that a traditional LDC model is overly optimistic and often produces power dispatches that do not lead to feasible AC power flows (the N-1 1 and N-17 are particularly striking). However, each refinement of the LPAC model solves more contingencies. The LPAC-R-V model is very reliable and is able to produce feasible dispatches in all contingencies except 3 from the N-1 1 case. This means that the LPAC-R-V model solves 99.98% of the 17,000 contingencies studied.

Table 9 depicts the load shed by the various models. For large contingencies, the LPAC-R-V model not only provides good starting points for an AC solver but its load shedding is only slightly larger than the (overly optimistic) LDC model. These results provide compelling evidence of the benefits of the LPAC model for applications dealing with situations outside the normal operating conditions. In addition, Model 4 can replace the LDC model in power restoration applications that are using MIP models to minimize the size of a blackout over time.

Table 9: Power Restoration: Average Load Shedding (% of Total Active Power),

Scenario LDC LPAC LPAC-R LPAC-R-V

N-3 0.653 1.376 4.507 4.578

2.483 3.341 6.966 7.019

N-5 1.312 2.186 5.864 7.01 1

N-6 4.271 7.652 18.8 18.87

N-7 4.825 5.075 9.762 10.35

N-8 47.15 47.22 47.82 48.14

N-9 11.4 13.57 25.22 25.35

N-10 11.92 12,02 16.75 18.4

N-l l 6.132 6.978 17.36 17.79

N-12 19.94 20.08 27.72 28.25

N-13 26.81 26.83 33.1 1 33.19

N-14 23.19 23.21 30.06 30.08

N-15 19.56 19.56 24.17 25.28

N-16 32.22 32.23 33.8 34.19

N-17 42.86 42.88 40.8 39.68

N-18 35.4 35.4 39.07 39.07

N-19 68.1 68.22 65.27 65.38

N-20 76.56 76.56 76.56 76.56 Capacitor Placement Problem based on LPAC Model

A simple version of the Capacitor Placement Problem (CPP) is used to demonstrate how the LPAC model can be used as a building block inside a MIP solver for decision- support applications.

Informally speaking, the CPP consists of placing capacitors throughout a power network to improve voltage stability. The version studied here aims at placing as few capacitors as possible throughout the network, while meeting a lower bound \ V \ on the voltages and satisfying a capacitor injection limit q ^c and reactive generation limits q ( e G) . Model 5 presents a CPP model based on the cold-start LPAC model. For each bus n , the additional decision variables are the amount of reactive support added by the capacitor q _n ^c and a variable c _n indicating whether a capacitor was used. Model 5: A Linear Program for Capacitor Placement

Inputs:

q - injection bound for generator n

q ^c - capacitor injection bound

\ V \ - minimum desired voltage magnitude

Inputs from Model 3 (Cold-Start)

Variables:

q € (0, q ^c ) - capacitor reactive injection

c _n e {0, 1 } - capacitor placement indicator

Variables from Model 3 (Cold-Start)

Minimize: Subject to:

\ ν \≤\Λ + φ _η < \ .05 V«€N ( ^Μ5 · ² )

q„ ^c ≤Mc _n (M5.3)

q„≤q ^~ * Vn e G ( ^Μ5 · ⁴ )

^(Μ5 · ⁵⁾ Constraints from Model 3 (Cold-Start) except for (M3.5)

The objective function (M5.1) minimizes the number of capacitors. Constraints (M5.2) ensure the voltages do not drop below the desired limit and do not exceed the preferred operating condition of 1.05 Volts p.u. Constraints (M5.3) link the capacitor injection variables with the indicator variables, a standard technique in MIP models. Constraints

(M5.4) ensures each generator n e G does not exceed its reactive generation limit q . and constraints (M5.5) defines the reactive power for generators. Lastly, Constraints (M5.6) redefines the reactive power equation to inject the capacitor contribution q ^c . The remainder of the model is the same as Model 3 (the cold-start LPAC model).

The CPP model was tested on a modified version of the IEEE57 benchmark. All of the IEEE benchmarks have sufficient reactive support in their normal state. To make an interesting capacitor placement problem, the transformer tap ratios are set to 1 .0 and existing synchronous condensers are removed. This modified benchmark (IEEE57-C) has significant voltage problems with several bus voltages dropping below 0.9. By design, a solution to Model 5 satisfies all of the desired constraints. However, Model 5 is based on the LPAC model and is only an approximation of the AC power flow. To understand the true value of Model 5, we solve the resulting solution network with an AC solver and measure how much the constraints are violated. Table 10 presents the results of Model 5 on benchmark IEEE57-C with q ^c - 30 and various thresholds \ V \ .

The table presents the following quantities: The minimum desired voltage | V | ; The worst violation of the voltage lower-bound min(| V |) ; The worst violation of the voltage upper bound max(| V |) ; The worst violation of reactive injection upper bound max(q _n ) ; The number of capacitors placed Ύ_ _η ; and the runtime of the MIP to prove the optimal placement solution. The table indicates that the CPP model is extremely accurate and only has minor constraint violations on the lower bounds of the voltage values. Table 10: Capacitor Placement Results on IEEE57-C, q ^c = 30 MVar

It is important to note that, although the CPP model can take as long as three minutes to prove optimality, it often finds the best solution value within a few seconds. The voltage lower bound approaches the value of 0.985 , which is the lowest value of the voltage-controlled generators in the benchmark. These results remain consistent for other voltage bounds. Once again, the CPP model indicates the benefits of the LPAC approximation for decision-support applications that need to reason about reactive power and voltages.

Comparisons

(a) Iterative Methods

Iterative methods, such as the fast-decoupled load flow, generally significantly reduce the computation time of solving the AC equations and demonstrate sufficient accuracy. Their disadvantage however is that they cannot be efficiently integrated into traditional decision-support tools. Indeed, MIP solvers require purely declarative models to obtain lower bounds that are critical in reducing the size of the search space.

Note however that, modulo the linear approximations, the LPAC model can be viewed as solving a decoupled load flow globally. Compared to the iterative methods,

1. Because the model forms one large linear system, all of the steps of the decoupled load flow are effectively solved simultaneously; 2. Because the formulation is a linear program, the values of and can now be decision variables, and bounds may be placed on the line capacities, voltage magnitudes, and phase angles;

3. The model may be embedded in a MIP solver for making discrete decisions about the power system.

In one or more embodiments, the second and third points represent significant advantages over the fast-decoupled load flow and other iterative methods. (b) Convex Models

Although many variants of the LDC model exist, few declarative models incorporate reactive flows in cold-start contexts. To the inventor(s)' knowledge, three cold-start approaches have been proposed: a polynomial approximation scheme, (2) a semi- definite programming relaxation, and (3) a voltage-difference model.

The polynomial approximation has the advantage of solving a convex relaxation of the AC power equations but the number of variables and constraints needed to model the relaxation "grows rapidly" and only second-order terms were considered. The accuracy of this approach for general power flows remains an open question. One approach focuses on a transmission planning application and does not quantify the accuracy of the approximation relative to an AC power flow.

The semi-definite programming (SDP) relaxation also has the advantage of solving a convex relaxation of the AC power equations. One approach demonstrated that the formulation finds the globally optimal value to the AC optimal power flow problem on a number of traditional benchmarks. This does not hold in general however. SDP solvers are also less mature than LP solvers and their scalability remains an open question. Finally, solvers integrating discrete variables on top of SDP models are very recent and do not have the scientific maturity of MIP solvers. The voltage-difference model has a resemblance to a model combining the equation with Equation (17). However, it makes a fundamental assumption that all voltages are the same before computing the voltage differences. In practice, voltage-controlled generators violate this assumption. On traditional power system benchmarks, we observed that the voltage-difference formulation had similar accuracy to the LDC model.

Section 3 - QPAC Model

This section introduces the QPAC model for approximating the AC power flow equations. A quadratically constrained model is first derived and a power flow feasibility problem presented.

The QPAC model, which is a convex quadratic approximation of the AC power flow equations, strikes a good compromise between accuracy and efficiency and may be embedded in general purpose discrete optimization solvers. In at least one example, the QPAC approximation also captures the effects of voltage magnitudes and reactive power. Moreover, the approximation is fundamentally driven by the behavior of power systems and the structure of the power flow equations. Although the QPAC model was inspired by a power restoration application, its implications are much broader. To demonstrate the broad applicability of the model, the QPAC approximation is evaluated on two example case studies of classic power system decision problems: optimal power flow (OPF) and capacitor placement problem. The experimental results show that the QPAC model provides an appealing tradeoff between accuracy and efficiency.

(a) Power flow feasibility problems

Model 6 presents a power flow feasibility problem based on the AC power flow equations which defines the space of feasible flows and forms a standard building block for many AC power flow optimization problem. An example power flow problem generally assumes the following: (1) load values s'„ = p„' + iq„' are fixed;

(2) the generators have bounded continuous operating range, i.e. s„ = p ^g + iq^ (lower bound), Sn = p + (upper bound);

(3) voltage magnitudes must remain within a continuous operating range, \ V_ \ (lower bound) | V | (upper bound);

(4) the lines have flow limits | S„ _m | .

Model 6: AC Power Flow Feasibility Problem

Model 6 presents a power flow feasibility problem based on the AC power flow equations. The inputs and decision variables are defined in the model. Many of the continuous operating limits of the network are captured in the variable bounds. The constraints are as follows: Constraint (M6.1 ) fixes the angle of the slack bus to eliminate some numerical symmetries. Constraint (M6.2) and (M6.3) enforce flow conservation (KCL) on each of the buses. Constraint (M6.4) and (M6.5) enforce Ohm's Law on each of the lines. Finally, constraint (M6.6) captures the line loading limit. Model 7 presents a power flow feasibility problem based on the traditional DC power flow equations. The latter equations only capture the flow of active power in the network and therefore must ignore constraints on reactive power and voltage magnitudes. The reduced inputs, decision variables, and constraints are defined in model 7.

Model 7: DC Power Flow Feasibility Problem

^■ Inputs:

(N, E, G, s) - the power network

- active injection limits for bus n

p«' > qn' - active and reactive demands at bus n

- susceptance of line nm

1 Snm 1 - thermal limit on line nm

Variables:

θ° 6 (-οο, οο) - phase angle on bus n (radians)

- active generation on bus n (MW p.u.)

Prim ^e ( ^~ l ΙΊ 1) - active flow on line nm (MW p.u.)

<ln _m = - \ V» \ ² b _m + \ V„ II v _m 1 b _nm cos(0; - ff _m \ v _* \\ v _m \ _Snm ύη ; - e _m ° )

Solve:

Θ: = o (M7.1)

Pn ~ Pn ~ Σ _< „ _)ΒΙ>€Ε Α»Η V« e N _. (M7.2) P„ _m - -b _nm {d: -e _m ^* ) \f{n, m) e E (M7.3)

(b) Power losses

The power loss on transmission line (n, m) is the absolute value of the difference between the amount of power sent at bus n and the one received at bus m .

Pl = P _nm + P _mn = g _nm (I V* I ² +1 V. \ ² -21 V„ II V _m I cos(6T - Θ: )) (18)

_. <7™ ^s = + <7™ = "Α Vn I ² + 1 I ² -21 II V _m I cos(^; - (19)

Explicitly factoring the power loss term in the power flow equations yields the equivalent line flow equations:

Note that although the LP AC model in Section 2 implicitly captures the power losses in the AC power flow equations, the power losses may be factored out and explicitly represented according to equations (20) and (21) in the LP AC model.

(c) Convex Quadratic Approximations

Tight convex approximations of the trigonometric functions involved in the power flow equations may be derived as follows. In one example, the second order Taylor expansions of the cosine and sine functions are used; see Fig. 8(a) and Fig. 8(b) respectively: cos(6>; - ) l - ^{(g: ~} ^ ⁾² (22) and

sino?; - ø;) * (ø; - ø;> (23) These approximations are quite accurate within the bounds -π 12 < θ° - 6 _m °≤ π 12 , which are generous given that typical operating bounds in power networks are ±π/35. Now, active and reactive power losses in equations (18) and (19) may be approximated respectively as follows:

= s»((l? ^» HK.l)^I r. ^|( ¾- ²

The next approximation step consists of replacing the voltage product | V„ \\ V _m \ by a given nominal value (e.g., 1 per unit) in all power equations, namely (18), (19), (20), and (21). Furthermore, in the power loss equations, artificial variables are introduced to convexify the quadratic equations, defining the convex feasible region as follows: v„ _M >(I^H^l) ² (24)

(25) p ^toss = a (v +( ) (26) q ^» =-b (v +t ) J (27)

Finally, in the power flow equations (20)-(21), we approximate the voltage square terms using a linear outer-approximation obtained by generating a tangent line around a given nominal value (e.g., 1 per unit) as shown in Fig.8(c), giving us

w _n ==2 _n |-l (28)

The complete QPAC approximation is defined by the system of constraints (24)-(30):

In summary, the approximations in this model are: (1) a second order Taylor approximation of sine and cosine terms; (2) a linear approximation of | V„ | ² ; (3) the simplification of voltage products | V„ \\ V _m |= 1.0 ; and (4) relaxing all quadratic equations into inequalities. These approximations exploit the nominal value of voltage magnitudes and phase angle differences, which allows us to exploit fundamental properties arising in the physics of power flows and hence to develop a convex approximation with unprecedented accuracy. (d) Convex Quadratic Feasible Power Flow

Building on (QPAC), Model 8 presents a power flow feasibility problem for given load and voltage limit on each bus, a set of generators with predefined injection limits and thermal capacity on connection lines. The problem consists of finding a flow satisfying Kirchhoff s law, the bound constraints and meeting all the desired loads. The inputs and decision variables are similar to the ones defined in Model 6. Variables p ^l ™ and q model respectively the active and reactive power loss on line (n, m) , while variables w, , v _nm , and i _nm define the convex relaxations of all quadratic terms found in the system (QPAC).

Model 8: QPAC Power Flow Feasibility Problem

(M8.9)

(M8.10)

PL ⁺ S»»> \ V(«, m> e £ (M8. l l )

Case Studies

This section describes two case studies to evaluate the potential of the QPAC model in decision-support applications in optimal power flow (a.k.a. economic dispatch) and capacitor placement. The goal is to provide evidence that the (QPAC) model strikes an appealing compromise between efficiency and accuracy on such applications. A comparison between DC, QPAC and the state-of-the-art LP AC model is performed.

It is important to emphasize that all of the power flow models under investigation (i.e. DC, LP AC, QPAC) are only approximations of the AC equations. Despite all of their computational advantages, they do not provide lower bounds on the objective values or ensure that their solution is feasible in the true AC system of equations. To understand the real-world practicality of these models, their outputs should be validated in the AC system of equations. This is achieved by first solving an optimization problem using the approximate model, followed by a validation step featuring the true non-convex nonlinear AC equations. The details of this procedure vary depending on the problem and are described in each case study.

All the optimization models were implemented in AMPL and use both CPLEX 12.5 and Sepa which implements an enhanced Outer-Inner approximation algorithm in Bonmin. The time limit was set to 3600 seconds. In Sepa, mixed-integer linear programs were solved using CPLEX 12.5. The non-convex and nonlinear programs are solved using Ipopt . All experimental results were performed on an Intel Xeon 1.6 Ghz CPU.

(a) Case Study 1 - Optimal Power Flow

The goal of the optimal power flow problem (OFF) is to find the cheapest way to generate power in order to satisfy customers' demand given some quadratic cost functions on generators. For each generator n G, the cost of generating power is defined by the quadratic function c"(p ) ² + c _n '(p ) + c _n . A classic OPF problem consist of minimizing the generation cost _neG ^c "(P ^{2 +c} _n '(P _n ) ^{+ c} _« subject to the AC feasibility constraints defined in Model 6.

For the QPAC model, the OPF problem may be formulated as follows:

Model 9: QPAC Optimal Power Flow Problem

The goal of this case study is not to demonstrate a new state-of-art-solution to the AC- OPF problem. Instead, we simply show that, on this class of problems the QPAC model is much more accurate than other existing approximations. This is done by first solving the OPF problem with an approximate model (i.e., the QPAC, the LPAC, or the DC model) and the OPF objective function. The OPF solution of these approximate models is converted into a feasible AC solution in the following way. Let p'* be the value of p* in the solution to the approximate OPF problem. We find the closest feasible AC solution by solving Model 6 with the objective function:

minimize : (p„' ^g - Ρ Ϋ·

We then measure how much the objective function has changed- in making the approximate solution AC feasible. In one example, a very small change may be preferable as it indicates that the approximation model led to an almost AC-feasible solution.

The accuracy results of all models are presented in Table 1 1 on 13 standard MatPower benchmarks. For each approximate power model a : O _a denotes the objective value in the approximate OPF problem; O the objective value of the nearest feasible AC solution; and 0[ _Q the best-known AC feasible objective value. Table 1 reports

for each model. The table indicates that the DC approximation has significant accuracy problems with a relative objective difference ranging from 1.45% - 6.20% . The LPAC model is significantly more accurate than the DC model in most cases with a relative objective difference below 5%. The QPAC model is the most accurate approximation with a relative objective difference always below 1%, This indicates that the QPAC model consistently finds nearly feasible solutions to the AC equations. A detailed runtime analysis for these methods is unnecessary as they all solve in a few seconds. Table 11: Accuracy of the Approximate Models on OPF Problems.

(b) Case Study 2 - Capacitor Placement

The Capacitor Placement Problem (CPP) is another well-studied application and many variants of the problem exist. This section uses a simple version of the problem to demonstrate how the QPAC model may be used as a building block inside a Mixed *

Integer Quadratic Program (MIQP) solver for power systems applications that feature discrete variables, a major computational challenge for existing technologies.

Informally speaking, the CPP consists of placing capacitors throughout a power network to improve the voltage profile. The version studied here aims at placing as few capacitors as possible, while meeting a lower bound \ V \ on the voltages and satisfying

— c — g

a capacitor injection limit q and reactive generation limits q _n (n G) .

Model 9 presents a CPP formulation based on the QPAC feasibility problem (Model 8). For each bus n e N , the additional decision variables are the amount of reactive support added by the capacitor q _n ^c and a variable c _n indicating whether a capacitor was placed at that bus.

Model 10: A QPAC-Based Capacitor Placement Problem,

The objective function (M10.1) minimizes the number of installed capacitors in the power network. Constraints (Ml 0.2) and Constraints (Ml 0.3) fix the active injection and voltage magnitudes of the generators while capacitor locations are considered. Constraints (Ml 0.4) prevent placement of capacitors at generation sites as they already have reactive injection capabilities. Constraints (Ml 0.5) ensure the voltages do not drop below the desired limit. Constraints (Ml 0.6) link the capacitor injection variables with the indicator variables. Finally, Constraints (Ml 0.7) redefines the reactive power balance equation to inject the capacitor contribution q _n ^c . The remainder of the model is the same as the QPAC feasibility problem (Model 8).

Once the approximate capacitor placement problem is solved, it is converted to a feasible AC solution by fixing the discrete variables c _n and solving a fully continuous AC feasibility problem. Note that there is no guarantee that there exists a solution to this AC feasibility problem. In fact, it will only be feasible if the approximation model was sufficiently accurate in the first phase, given the lack of truly global convergence properties of nonlinear continuous solvers.

The CPP model was tested on a modified version of the MatPower 57-bus benchmark. All of the MatPower benchmarks have sufficient reactive support in their given configurations. To make an interesting capacitor placement problem, the transformer tap ratios are set to 1.0 and existing synchronous condensers are removed. This modified benchmark (MatPower 57-bus-C) has significant voltage problems with several bus voltages dropping below 0.9 volts p.u..

Table 12: Performance of the Approximate Models on the CPP.

(a) Accuracy

Table 12(a) presents the results of the approximation models on benchmark MatPower 57-bus-C with q ~ 30 and various thresholds of | V j . The table presents the objective value (i.e. the minimum number of capacitors placed) for the non-convex nonlinear AC version of the problem, a convex LP AC version of the problem, and a convex QPAC version presented here. The results indicate that the QPAC is highly accurate, while the LP AC has some accuracy limitations. In all cases the QPAC model places the same number of capacitors as the AC model, while the LP AC typically suggests one additional capacitor (due to approximation inaccuracy). Both LP AC and QPAC may be converted into feasible AC solutions, with the only exception being the LPAC model with a voltage bound of | V | = 1.025 , in this case, the selected locations do not lead to a feasible AC solution. Table 12(b) presents the runtime results of the CPP experiment in detail. The non- convex nonlinear AC model is solved using the nonlinear Branch & Bound algorithm implemented in Bonmin as a heuristic. In this case, there is no optimality guarantees at each node of the Branch & Bound tree and the global algorithm may cut optimal integer solutions. The QPAC and LPAC models are studied with two solving technologies, the MISOCP solver implemented in CPLEX 12.5 and SEPA, an Outer- Inner approximation method exploiting function separability of the quadratic constraints. Regardless of the solving technology, both models are able to prove optimality in less than an hour. There are three key messages in this case study. 1. The LPAC and QPAC models are orders of magnitude more scalable than the nonlinear branch and bound algorithm using the AC power flow equations. The "heuristic" algorithm is in fact plagued by numerical issues with the underlying nonlinear solver, failing to solve nonlinear subproblems on different nodes of the branching tree.

2. The nonlinear branch and bound is purely heuristic: It does not provide any optimality guarantee. The LPAC and QPAC models, in contrast, prove optimality of the solution within the confines of their approximations. 3. The QPAC model is more accurate than the LPAC model, often reducing the number of capacitors used. Moreover, this additional accuracy comes at a reasonable cost in efficiency, striking a good tradeoff between accuracy and efficiency. The QPAC model does not experience numerical issues thanks to the convexity of the feasible region and benefits from scalable mixed-integer linear techniques such as outer- Approximation approaches.

These results on the CPP are particularly encouraging as they demonstrate several cases where the QPAC model can very quickly prove optimality of the model and convert the resulting solution into a high-quality AC-feasible solution. However, it is important to recall that the QPAC (and its competitors) have two limitations: (1) they are only approximations of the AC power flows and do not produce true lower bounds on the objective value; (2) they are convex relaxations of the non-convex equations, thus it is always possible to produce solutions that are inside the convex region. Interestingly, the applications studied here indicate these limitations are not a major issue. The success of the DC power flow approximation suggests that, despite its limitations, the QPAC can still have a profound impact on real-world power system operations.

To summarise, approximations of the AC power flow equations may be broadly grouped into iterative methods and convex models.

Iterative methods, such as the fast-decoupled load flow, significantly reduce the computation time of solving the AC equations and demonstrate sufficient accuracy. Their disadvantage however is that they cannot be efficiently integrated into traditional decision-support tools. Indeed, MIP solvers require purely declarative models to obtain lower bounds that are critical in reducing the size of the search space. Although many variants of the DC model exist, few declarative models incorporate reactive flows in cold-start contexts.

In one example, polynomial approximation has the advantage of solving a convex relaxation of the AC power equations but the number of variables and constraints needed to model the relaxation "grows rapidly'" and only second- order terms were considered. The accuracy of this approach for general power flows remains an open question as reference focuses on a transmission planning application and does not quantify the accuracy of the approximation relative to an AC power flow. In another example, semi-definite programming (SDP) relaxation is purely syntactic. It has the great advantage that it can sometimes solve the power flow equations optimally, without any approximation. In fact, it has been demonstrated that the SDP formulation finds the globally optimal value to the AC optimal power flow problem on a number of traditional benchmarks. However, recent work has shown that this does not hold on some practical examples. Computationally, SDP solvers are also less mature than QP solvers and their scalability remains an open question. Solvers integrating discrete variables on top of SDP models are very recent and do not have the scientific maturity of convex MINLP solvers.

At least in one example, the LP AC model is slightly faster than QPAC as it only uses (mixed-integer) linear optimization technology, rather than (mixed-integer) convex nonlinear optimization technology. Nevertheless, the QPAC model provides greater accuracy, keeping in mind that even small improvements in accuracy can save millions of dollars annually in some applications.

Processing Unit 1 10

The example method in Fig. 2 and Fig. 3 can be implemented by hardware, software or firmware or a combination thereof. Referring to Fig. 9, an example structure of a processing device 900 capable of acting as a processing unit 1 10 is shown in Fig. 1.

The example device 900 includes a processor 910, a memory 920 and a network interface device 940 that communicate with each other via a communication bus 930. Information may be transmitted and received via the network interface device 940, which may include one or more logical or physical ports that connect the device 900 to another network device. For example, the various methods, processes and functional units described herein may be implemented by the processor 910. The term 'processor' is to be interpreted broadly to include a CPU, processing unit, ASIC, logic unit, or programmable gate array etc. The processes, methods and functional units may all be performed by a single processor 910 or split between several processors (not shown in Fig. 9 for simplicity); reference in this disclosure or the claims to a 'processor' should thus be interpreted to mean 'one or more processors'. Although one network interface device 940 is shown in Fig. 9, processes performed by the network interface device 940 may be split between several network interface devices. As such, reference in this disclosure to a 'network interface device' should be interpreted to mean One or more network interface devices". The processes, methods and functional units may be implemented as machine-readable instructions executable by one or more processors, hardware logic circuitry of the one or more processors or a combination thereof. In the example in Fig. 9, the machine- readable instructions 924 are stored in the memory 920, Other information 922 such as input information, constraints and/or variables computed by the processing unit 1 10 may be stored in the memory 920, or remote data stores (not shown in Fig. I).

Further, the processes, methods and functional units described in this disclosure may be implemented in the form of a computer program product. The computer program product is stored in a computer-readable storage medium and comprises a plurality of computer-readable instructions for making a device 700 implement the methods recited in the examples of the present disclosure.

The figures are only illustrations of an example, wherein the units or procedure shown in the figures are not necessarily essential for implementing the present disclosure. Those skilled in the art will understand that the units in the device in the example can be arranged in the device in the examples as described, or can be alternatively located in one or more devices different from that in the examples. The units in the examples described can be combined into one module or further divided into a plurality of sub- units. Although the flowcharts described show a specific order of execution, the order of execution may differ from that which is depicted. For example, the order of execution of two or more blocks may be changed relative to the order shown. Also, two or more blocks shown in succession may be executed concurrently or with partial concurrence. All such variations are within the scope of the present disclosure.

It should also be understood that, unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as "optimising", "classifying", "constructing", "receiving", "processing", "retrieving", "selecting", "calculating", "determining", "optimising", "displaying" or the like, refer to the action and processes of a computer system, or similar electronic computing device, that processes and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices. Unless the context clearly requires otherwise, words using singular or plural number also include the plural or singular number respectively.

It will be appreciated by persons skilled in the art that numerous variations and/or modifications may be made to the above-described embodiments, without departing from the broad general scope of the present disclosure. The present embodiments are, therefore, to be considered in all respects as illustrative and not restrictive.