Observing the State of a Smart Grid Using Bilevel Programming

Abstract

Monitoring an electrical network is an important and challenging task. Phasor measurement units are measurement devices that can be used for a state estimation of this network. In this paper we consider a PMU placement problem without conventional measurements and with zero injection nodes for a full observability of the network. We propose two new approaches to model this problem, which take into account a propagation rule based on Ohm’s and Kirchoff’s law. The natural binary linear programming description models an iterative observability process. We remove the iteration by reformulating its fixed point conditions to a bilevel program, which we then further reformulate to a single-level mixed-integer linear program. We also present a bilevel algorithm to solve directly the proposed bilevel model. We implemented and tested our models and algorithm: the results show that the bilevel algorithm is better in terms of running time and size of instances which can be solved.

1 Introduction

One of the properties making a grid smart is that its state is continuously monitored. The term state is an abstract concept which may be represented in many ways. We consider that a state of a grid is the set of values of all the branch currents and node voltages. Monitoring the state of a grid can be achieved using tools of measurement and control. A piece of equipment which can be used is Phasor Measurement Unit (PMU). PMUs are monitoring devices that provide time synchronized phasor measurement (a phasor is a complex number that represents both the magnitude and phase angle of the sine waves found in electricity). A PMU placed at a (sub)station measures the voltage and phase angle of this (sub)station and branch current phasor of all transmission line emerging from it [11]. PMUs are synchronized via global positioning systems (GPS) and send large bursts of data to a system monitoring centre. Due to the relatively high cost of PMUs, their optimal placement constitutes an important challenge.

Modelling the network by a graph where nodes correspond to (sub)stations and edges to transmission lines, the optimal location problem of PMUs, called PMU placement problem, consists of determining the minimum number of PMUs to place on the nodes, in order to ensure a full observability of the graph. A graph is said fully observed if the voltage is known at each node, and the current known on each edge. In [2], the observability of a graph is defined by two rules: (i) if a node has a PMU then this node and all its neighbours are observed; (ii) if an observed node has all its neighbours observed, except one, then this latter is observed. The PMU placement problem is also known as power dominating set (PDS) problem [8]. This problem has been largely studied in literature. The PDS is shown to be NP-complete even for bipartite, chordal graphs [8] and planar bipartite graphs [2], and polynomial for trees and grids [4]. Some approximation results are presented in [1]. Different solution methods have been proposed to solve the PMU placement problem [11, 12]. In all these approaches, the propagation rule has been considered for the zero injection nodes with a limited depth.

The PMU placement problem has also been studied for PMUs with limited channels $\ell$ where only a limited number of incident transmission lines can be observed [9, 10]. Korkali and Abur propose a binary linear program considering for each node of the graph all the possible combinations of $\ell$ edges among incident edges of that node [9]. The number of combinations can be exponential. Kumar and Rao propose a new method to solve PMU placement problem based on node connectivity and edge selectivity matrices where the number of channels are less than the minimum degree of the graph [10]. For PMUs with one channel, only one incident line can be observed. The placement of PMUs is then no more on nodes but on edges. The first rule of observability is then: if an edge has a PMU then its extremity nodes are observed. Emami et al. propose a binary linear program for this variant of the problem [5, 6], which turns out to be equivalent to the minimum edge cover problem. They consider the second rule of observability defined in [2] for zero injection nodes with only one depth.

We propose in this paper a new approach to model the optimal location of PMUs with one channel. We place PMUs on edges (next to one of the adjacent nodes) and take into account both rules of observability. We call this particular variant the Power Edge Set (PES) problem. More specifically, we consider the case without conventional measurements (measures provided by non synchronized sensors) and all nodes are zero injection nodes (no current is injected in the network at those nodes). We present two mathematical formulations for this problem: iterative and bilevel models; the latter can be formally inferred from the former by means of a fixed-point argument. The former is a Binary Linear Program. We show that the latter can be reformulated exactly to a Mixed-Integer Linear Program (MILP) with binary variables, and also propose a cutting-plane algorithm to solve it in its native bilevel formulation. We benchmarked our solution methods on standard IEEE bus-systems [14] and randomly generated graphs.

2 Problem Statement

Let $G=(V,E)$ be a graph modelling the electrical network where $V=\{1,\ldots ,n\}$ is the set of nodes representing the (sub)stations and E the set of edges corresponding to transmission lines. For $i \in V$, $\varGamma (i)=\{j: \{i,j\} \in E\}$ is the set of neighbours (adjacent nodes) of i. For graph-theoretical notions, see [7, 13].

In this paper, we are interested in the optimal placement of PMUs with one channel, so as to ensure a full observability of G. We consider that no conventional measures exist, which would reduce the number of PMUs to install.

A PMU is placed on an edge $\{i,j\}$ close to node i, for $i \in V$ and $\{i,j\} \in E$.

We remark that the fact that PMU placement occurs closer to an adjacent node than the other is relevant for physical reasons, but irrelevant for our abstract modelling purposes. Henceforth, we shall simply assume that placement occurs on an edge $\{i,j\}\in E$. A graph is said to be observable if all node voltages and current edges are known either measured by a PMU or estimated using electrical laws. The problem is defined as follows:

2.1 Observability of a Graph

Let $\varPi$ be a given PMU placement on G and $\varOmega$ the set of observed nodes. The observability of G is defined by the two following rules based on electrical laws explained below.

• R1: If a PMU is placed on an edge $\{i,j\}$, then nodes i and j are observed

  $$\begin{aligned}\{i,j\} \in \varPi \Rightarrow i,j\in \varOmega \end{aligned}$$

• R2: If an observed node i has all its neighbors observed, save one, then this node is observed

  $$\begin{aligned}i \in \varOmega \,{\text {and}}\,|\varGamma (i)\setminus \varOmega | \le 1 \Rightarrow \varGamma (i) \subseteq \varOmega \end{aligned}$$

By rule R1, the PMU placed at $\{i,j\}$ measures the voltage at i and the current on $\{i,j\}$. Using Ohm’s law, we can deduce the voltage on j. Then i and j are observed. By rule R2, if a node i and all its neighbors $k \in \varGamma (i)$ are observed, except a single node j, then using Ohm’s law we can determine the current on $\{i,k\}$ for $k\in \varGamma (i)\setminus \{j\}$; knowing the currents on all $\{i,k\}$ (for $k\not =j$) we can deduce the current on $\{i,j\}$ using Kirchoff’s law. Then, knowing the voltage at i and the current on $\{i,j\}$, we determine the voltage on j using Ohm’s law. Hence, j is observed.

3 Mathematical Modelling

We present two Mathematical Programming (MP) models for PES problem: an iterative based model, and a bilevel one.

3.1 Iterative Model

The model is based on the iterative process of observability given by rules R1 and R2. Assuming the problem instance to be a feasible one, the set of observed nodes can be found in at most $n-2$ steps: this is because, in the worst case, only one PMU is placed on an edge (this observes the adjacent nodes), and one more node is observed at each iteration. Let $T=n-2$ be the maximum number of steps. The iterative model $(P_{\text{ IT }})$ is as follows.

Variables. We define the following set of variables:

$$\begin{aligned}&\forall i \in V, j \in \varGamma (i), \;\;\; s_{ij} = \left\{ \begin{array}{lll} 1 &{}\text {if a PMU is installed on } \{i,j\} &{}\\ 0 &{} \text {otherwise}&{} \end{array} \right. \\&\forall i \in V, t=0,\ldots ,T, \;\;\; \omega _{it} = \left\{ \begin{array}{lll} 1 &{}\text {if the node { i} is observed at step { t}} &{}\\ 0 &{} \text {otherwise}&{} \end{array} \right. \\&\,{\text {and}}\, \forall i \in V, j \in \varGamma (i),t=0,\ldots ,T-1,\\&y_{ijt} = \left\{ \begin{array}{lll} 1 &{}\text {if}~{ R}2~ \text {is used to observe} \,{ j}\, \text {using the observed node}\, { i}\, \text {at step}\, { t} &{}\\ 0 &{} \text {otherwise.} \end{array} \right. \end{aligned}$$

Constraints. The set of constraints is the following:

• All nodes must be observed at step T

  $$\begin{aligned}\forall i \in V, \; \; \; \omega _{iT}=1\end{aligned}$$

• If a node i is observed at step 0 then at least one PMU is placed at $\{i,j\}$ or $\{j,i\}$ for a given neighbour j of i

  $$\begin{aligned}\forall i \in V, \; \; \; \omega _{i 0} \le \underset{j \in \varGamma (i)}{\sum } (s_{ij}+s_{ji})\end{aligned}$$

• The set of constraints corresponding to rule R2 is the following:

  • If i not observed at step t is observed at step $t+1$ then at least one neighbour observed node has been used to observe i

    $$\begin{aligned}\forall i \in V, t=0,\ldots ,T-1, \;\;\; \omega _{i(t+1)} \le \omega _{it}+\underset{\ell : i \in \varGamma (\ell )}{\sum } y_{\ell i t}\end{aligned}$$

  • If an observed node i is used at step t to observe a neighbour node j and j is observed at step $t+1$ then j is not observed at step t

    $$\begin{aligned}\forall i \in V, j \in \varGamma (i), t=0,\ldots ,T-1 , \;\;\; \omega _{j(t+1)} +y_{ijt}\le \omega _{jt}+\omega _{it}+1\end{aligned}$$

  • If an observed node i is used at step t to observe a neighbour node j and j is observed at step $t+1$ then j is not observed at step t and all the other neighbour nodes k of i are observed at step t

    $$\begin{aligned}\forall i \in V, j,k \in \varGamma (i), k\ne j, t=0,\ldots ,T-1, \;\;\; \omega _{j(t+1)} +y_{ijt}\le \omega _{jt}+\omega _{kt}+1\end{aligned}$$

• If a node i is observed at step t then i is observed from step t to step T

  $$\begin{aligned}\forall i \in V, t=0,\ldots ,T-1, \;\;\; \omega _{it} \le \omega _{i(t+1).} \end{aligned}$$

Objective Function. The aim of PES problem is to minimize the number of PMUs to install and that allow a full observability of G. Hence the objective function is given by

$$\begin{aligned} \min \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij}. \end{aligned}$$

3.2 From Iterative to Bilevel Model

We show in this subsection how to deduce a bilevel model from the iterative one using a fixed-point method.

Let $\omega ^t=(\omega _{it}\;|\;i\in V)$ be the characteristic vector describing the observability of nodes at step t. The iterative model computes the vector values for $t\in \{1,\ldots ,T\}$. Let $\omega =(\omega _{i}\;|\;i\in V)$ be the characteristic vector of $\varOmega$:

$$\begin{aligned} \forall i \in V, \;\;\; \omega _{i} = \left\{ \begin{array}{lll} 1 &{}\text {if node } i \text { is observed} &{}\\ 0 &{} \text {otherwise.}&{} \end{array} \right. \end{aligned}$$

We have that $\omega =\omega ^T$. We show now how to obtain a non iterative model where $\omega$ are the only variables that model the observability of the graph.

Let $t\le T$ and i a node in V. The recursive relation that allows to express $\omega _{i(t+1)}$ in function of $\omega _t$ is:

$$ \omega _{i(t+1)}= \max \left( \omega _{it},\max _{j \in \varGamma (i)}\left( 1-|\varGamma (j)|+\omega _{jt}+\sum _{k\in \varGamma (j),k\ne i}\omega _{kt}\right) \right) $$

meaning that a node i is observed at step $t+1$ if it was already observed at step t or if there exists a neighbour j of i such that all the other neighbours $k \ne i$ of j are observed.

Let $\theta \ :\ \{0,1\}^n \mapsto \{0,1\}^n$ be a function where

$$\forall i \in V, \theta _i(x)= \max \left( x_i,\max _{j \in \varGamma (i)}\left( 1-|\varGamma (j)|+x_j+\sum _{k\in \varGamma (j),k\ne i}x_k\right) \right) .$$

with $x=(x_i\;|\;i \in V)$ and $(\theta (x))_i=\theta _i(x)$.

By definition we have that:

$$\begin{aligned} \forall t\in \{1,\ldots ,T-1\}\quad \omega ^{(t+1)}=\theta (\omega ^t). \end{aligned}$$

Recursive Computation of $\omega$ : The vector $\omega$ is determined recursively as follows:

• Based on R1, for $t=0$ we have:

  $$\forall i \in V,\ \omega _{i0} =\max (\max _{j \in \varGamma (i)} s_{ij}, \, \max _{j \in \varGamma (i)} s_{ji})$$

• Knowing $\omega ^t$, we can compute $\omega ^{(t+1)}$ by looking for an optimal solution of the linear program:

  $$\begin{aligned} (*)\quad \left\{ \begin{array}{rrcl} \underset{\omega ^{t+1} \in \{0,1\}^n}{\min }&{} \sum \limits _{i=1}^n \omega _{i(t+1)} &{} &{}\\ \forall i \in V &{} \omega _{i(t+1)} &{}\ge &{} \omega _{it}\\ \forall i \in V,\ j \in \varGamma (i) &{} \omega _{i(t+1)} &{}\ge &{} 1-|\varGamma (j)|+\omega _{jt}+\sum \limits _{k\in \varGamma (j)\atop k\ne i}\omega _{kt}. \end{array} \right. \end{aligned}$$

Theorem 1

We have that $\omega$ is the smallest fixed point of $\theta$.

Proof

By the definition of the function $\theta$, we have that $\theta _i(\omega )\ge \omega _i, \forall i \in V.$

Suppose that $\exists i \in V,$ $\theta _i(\omega )> \omega _i$ i.e. $\omega _i=0$ and $\theta _i(\omega )=1$. Then $i \in \varOmega$ by an application of R2 which implies $\omega _i=1 >0 = \omega _i$, contradiction. Hence $\theta (\omega )=\omega$.

Assume now that $\exists \omega ' < \omega : \omega '=\theta (\omega ')$. This means that R2 cannot be used to observed more nodes. Hence the number of nodes observed in $\omega '$ is less then the one in $\omega$, i.e. $\underset{i \in V}{\sum }\omega '_i < \underset{i \in V}{\sum }\omega _i$ which contradict the optimality of $(*)$.

Therefore, $\omega$ is the smallest fixed point of $\theta$ and correspond to the optimal solution of the following linear program:

$$\begin{aligned} \left\{ \begin{array}{lll} \underset{\omega \in \{0,1\}^n}{\min }&{} {\sum }_{i=1}^n \omega _{i} &{} \\ &{} \omega _i \ge s_{ij} + s_{ji}\ \ \ &{} \forall i \in V,\ j \in \varGamma (i) \\ &{} \omega _i -\omega _j - \underset{k \in \varGamma (j), k \ne i}{\sum }\omega _k \ge 1-|\varGamma (j)|\ \ \ \ &{} \forall i \in V,\ j \in \varGamma (i) \end{array} \right. \end{aligned}$$

$\square$

3.3 Bilevel Model

We describe in this subsection the bilevel program proposed to model the PES problem. We also show how it can be reformulated to a MILP.

The formulation

$$\begin{aligned} (\dag )\quad \left\{ \begin{array}{lll} \underset{s}{\min }&{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij} &{}\\ &{} s_{ij} \in \{0,1\} \;\;\; \quad \quad \forall i \in V, j \in \varGamma (i)&{}\\ &{} f(s) \ge n &{}\\ &{} f(s)= \left\{ \begin{array}{ll} \min \limits _{\omega } \underset{i \in V}{\sum }\omega _i &{}\\ \omega _{i} \ge s_{ij} + s_{ji} &{} \forall i \in V, j \in \varGamma (i)\\ \omega _{i} - \omega _{j} - \underset{k \in \varGamma (j), k \ne i}{\sum } \omega _{k} \ge 1-|\varGamma (j)| &{} \forall i \in V, j \in \varGamma (i)\\ \omega _{i} \in \{0,1\} &{} \forall i \in V \end{array}\right. \end{array} \right. \end{aligned}$$

In the upper level problem, the objective is to minimize the number of PMUs to install such that the number of observed nodes given fy the function f(s) is at least n. The function f corresponds to the optimal value of the lower level problem described below and s is the vector representing $s_{ij}$.

In the lower level problem, the objective is to minimize the number of nodes observed. The first set of constraints says that if a PMU is placed at $\{i,j\}$ or $\{j,i\}$ then i and j are observed. The second expresses the propagation rule R2: if a non observed node i has an observed neighbour j that has all its others node neighbours $k (k\ne i)$ observed then i is observed.

MILP Reformulation. The integrality of variables $\omega _i$ can be relaxed in the lower level problem.

Lemma 1

For each $i\in V,$ the constraint $\omega _{i} \in \{0,1\}$ can be replaced by $\omega _{i} \ge 0$.

Proof

Let $\bar{\omega }$ be an optimal solution of the slave problem and consider a certain configuration of installed PMUs in the graph.

By the first constraint

$$\begin{aligned} \omega _i\ge s_{ij}+s_{ji}, \; \forall i \in V, j\in \varGamma (i) \end{aligned}$$

(1)

we have that $\exists S \subseteq V, \forall i \in S, \bar{\omega _i}=1$. If we rewrite the second constraint of the slave problem as

$$\forall i \in V, j \in \varGamma (i), \;\;\; \omega _{i} \ge \omega _{j} + \underset{k \in \varGamma (j), k \ne i}{\sum } \omega _{k} -|\varGamma (j)| +1$$

we have that the right hand side $r(\bar{\omega }) \in [1-|\varGamma (j)|, 1]$.

If $r(\bar{\omega }) \in ]0,1[$ then $\exists z \in \varGamma (j) \cup \{j\} : \bar{\omega _z} \in ]0,1[$. Hence, $\exists Z \subseteq V, \; \forall z \in Z: \; \bar{\omega _z} \in ]0,1[$. Also, $\forall z \in Z$, z is not constrained by (1) otherwise $\bar{\omega _z}=1$. By the objective function direction, $\forall z \in Z$ we can set $\bar{\omega _z}=0$ and still be feasible, which contradict the optimality of $\bar{\omega }$. Therefore, we can relax the integrity of variables $\omega$ to $[0,1]^n$.

Similarly, we can prove that $\forall i \in V, \omega _i \ge 0$.$\square$

Hence, by replacing the lower-level problem by its KarushKuhnTucker (KKT) conditions [3], we obtain the following MILP:

$$\begin{aligned} (P) \left\{ \begin{array}{lll} \underset{s}{\min }&{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij} &{}\\ ~\\ &{} s_{ij} \in \{0,1\} &{} \forall i \in V, j \in \varGamma (i)\\ ~\\ &{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij} \mu _{ij}+s_{ji}\mu _{ij} +(1-|\varGamma (j)|)\lambda _{ij} \ge n&{} \\ ~\\ &{} \underset{j \in \varGamma (i)}{\sum } ( \mu _{ij} + \lambda _{ij}-\lambda _{ji} - \underset{k \in \varGamma (j),k\ne i}{\sum } \lambda _{kj} ) \le 1&{} \forall i \in V \\ ~\\ &{} \lambda _{ij}, \mu _{ij} \ge 0&{} \forall i \in V, j \in \varGamma (i) \end{array} \right. \end{aligned}$$

We now prove that the dual variables $\mu _{ij}$ are bounded, $\forall i \in V,j \in \varGamma (i)$.

Proposition 1

$\forall i \in V,\; j \in \varGamma (i), \; \exists M>0 : \;\mu _{ij}\le M$.

Proof

Let $(s^*,\mu ^*,\lambda ^*)$ be an optimal solution of (P) and $(s^*,\omega ^*)$ be the corresponding optimal solution of the bilevel formulation. In particular, we consider $(s^*,\mu ^*,\lambda ^*)$ such that $(\mu ^*,\lambda ^*)$ is a basis solution of the dual program of the linear program that defines f:

$$\begin{aligned} \left\{ \begin{array}{lll} \underset{s}{\max }&{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij} \mu _{ij}+s_{ji}\mu _{ij} +(1-|\varGamma (j)|)\lambda _{ij} \\ &{} \underset{j \in \varGamma (i)}{\sum } ( \mu _{ij} + \lambda _{ij}-\lambda _{ji} - \underset{k \in \varGamma (j),k\ne i}{\sum } \lambda _{kj} ) \le 1&{} \forall i \in V \\ &{} \lambda _{ij}, \mu _{ij} \ge 0&{} \forall i \in V, j \in \varGamma (i) \end{array} \right. \end{aligned}$$

Necessarily at most n dual variables are non-zero. Let $I=\{(i,j)\ |\ \mu _{ij} \ne 0 \}$ and $J=\{(i,j)\ |\ \lambda _{ij} \ne 0 \}$. We have $|I|+|J|\le n$.

Let $i\in \{1,...,n\}$ such that $\omega ^*_i=1$. By complementary slackness conditions we have

$$\begin{aligned} \underset{j \in \varGamma (i)}{\sum } ( \mu ^*_{ij} + \lambda ^*_{ij}-\lambda ^*_{ji} - \underset{k \in \varGamma (j),k\ne i}{\sum } \lambda ^*_{kj} ) =1 \end{aligned}$$

(2)

Let $A_B \in {\mathbb {R}^{n \times n}}$ be the basis matrix corresponding to the optimal solution $(\mu ^*,\lambda ^*)$. By Eq. (2), $v=(\mu ^*,\lambda ^*,\beta ^*)$ is a solution of the system $A_B \;v=e$, where $\beta ^*$ denotes the slack variables used to write the above dual program in standard form, e is a vector in $\mathbb {R}^n$ where each component is one, and all elements of $A_B$ are in $\{-1,0,1\}$.

Since $A_B^{-1}=\frac{\text{ adj }(A_B)}{\det (A_B)}$, where $\text{ adj }(A_B)$ is the adjugate matrix of $A_B$ and $det(A_B)$ is the determinant of $A_B$, using Hadamard inequality for determinant, we obtain that the dual variables $\mu _{ij}$ are all bounded by $M=n^{\frac{n}{2}}$, $\forall i \in V, j \in \varGamma (i)$.$\square$

By Proposition 1, we can linearize the program (P) by replacing the variable products by $\forall i \in V, j \in \varGamma (i),$ $p_{ij}= s_{ij} \mu _{ij}$ and $q_{ij}=s_{ji}\mu _{ij}$. Therefore, we obtain the MILP $(P_{\text{ MILP }})$.

$$\begin{aligned} (P_{\text{ MILP }}) \quad \left\{ \begin{array}{lll} \min &{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } s_{ij} &{}\\ &{} s_{i,j} \in \{0,1\} &{} \forall i \in V, j \in \varGamma (i)\\ &{} \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } p_{ij}+ q_{ij} +(1-|\varGamma (j)|)\lambda _{ij} \ge n&{} \\ &{} \underset{j \in \varGamma (i)}{\sum } ( \mu _{ij} + \lambda _{ij}-\lambda _{ji} - \underset{k \in \varGamma (j),k\ne i}{\sum } \lambda _{kj} ) \le 1&{} \forall i \in V \\ &{} p_{ij} \le M\;s_{ij}&{} \forall i \in V, j \in \varGamma (i)\\ &{} p_{ij} \le \mu _{ij} &{}\forall i \in V, j \in \varGamma (i) \\ &{} p_{ij} \ge \mu _{ij} -M(1-s_{ij}) &{}\forall i \in V, j \in \varGamma (i)\\ &{} q_{ij} \le M \; s_{ji} &{}\forall i \in V, j \in \varGamma (i)\\ &{} q_{ij} \le \mu _{ij} &{}\forall i \in V, j \in \varGamma (i)\\ &{} q_{ij} \ge \mu _{ij} -M(1-s_{ji}) &{}\forall i \in V, j \in \varGamma (i)\\ &{} \lambda _{ij}, \mu _{ij} \ge 0&{} \forall i \in V, j \in \varGamma (i) \end{array} \right. \end{aligned}$$

4 An Algorithm for the Bilevel Problem

We propose a cutting plane algorithm BiLevelSolve to solve the bilevel program ($\dag$) directly. BiLevelSolve iteratively solves a modified version of the upper level problem as a master MILP, adding a new cut at each iteration. The cuts are generated by means of the combinatorial procedure GenerateCut on the lower level slave problem.

Consider the following MILP $P^k$:

$$\begin{aligned}{}[P^k] \quad \left\{ \begin{array}{rrcl} \min \limits _{s\in \{0,1\}^{|E|}} &{} \sum \limits _{i\in V}\sum \limits _{j\in \varGamma (i)} s_{ij} &{}&{} \\ \forall h\le k&{} \alpha ^h s &{}\ge &{} 1, \end{array}\right. \end{aligned}$$

(3)

where $\alpha ^h\in \{0,1\}^{|E|}$ for each $h\le k$, and k is the main algorithm iteration counter: at iteration k, $P^k$ has k linear covering constraint, starting with $\alpha ^1=(1,\ldots ,1)$.

Although BiLevelSolve needs exponentially many cuts in the worst case, we found it to perform very well empirically.

5 Computational Results

All the experimentations presented here were performed on a 2.70 GHz computer with 8.0 GB RAM. The models $(P_{\text{ IT }})$, $(P_{\text{ MILP }})$ and the bilevel algorithm were implemented using IBM ILOG CPLEX 12.6. We considered as instances a 5-bus system and standard IEEE n-bus systems, with $n \in \{7, 14, 30,57, 118\}$ [14]. We also generate randomly graphs with n nodes and $m=1.4 \times n$ for $n=\{5\times i, i=1,\ldots ,10\}$ where 1.4 is the average rate of edges over nodes in standard IEEE bus systems. The instances can be forests and no node is isolated. For each value of n, 10 different instances were generated and tested. The results obtained are reported in Table 1 where each given value for the randomly generated graphs is the average over 10 instances. We limited the running time to 2 h. For any instance which is not solved optimally within the time limit, the running time is set to this limit. We reported: (i) the Gap, expressed as a percentage, that is the average over ratios $\frac{UB\; - \;BS}{UB}$ computed on all instances returning at least one feasible solution, where UB is the final best upper bound and BS is the best solution value found; and (ii) the number of instances #opt solved optimally, and the number of instances that run out of memory (mof, for memory overflow).

Table 1. Computational results

We note that the iterative model cannot be used to solve medium and larger size instances. The MILP model can solve instances with more larger size than the iterative one but cannot solve large size instances. The bilevel algorithm can solve almost all the instances considered in few seconds. It did not solve only 4 instances of the random generated graphs considered within the time limit. For small instances, MILP performs a little better than the bilevel. This is due to the choice of the solution selected at each iteration to generate the cutting plane in the bilevel algorithm. Hence some iterations may be needed to converge to the optimal solution in the bilevel algorithm while in the MILP model, having a small number of variables and constraints for those instances, the model converges in few seconds.

Therefore the bilevel algorithm is better in terms of running time and size of instances that can be solved.

Remark 1

We assumed here that the installation cost is the same for every PMU location at a node along an edge. If not, the problem consists then in finding the placement of PMUs that ensures a full observability of the graph and minimize the total installation cost. Let, $\forall i \in V, j \in \varGamma (i)$, $c_{ij}$ be the cost of installing a PMU on $\{i,j\}$ at i. The new objective function is then given by:

$$\begin{aligned} \min \underset{i \in V}{\sum }\underset{j \in \varGamma (i)}{\sum } c_{ij} \; s_{ij} \end{aligned}$$

Remark 2

The models proposed for PMU placement problem, where PMUs are with unlimited number of channels and hence the placement is done on nodes, do not consider the propagation rule too. Our proposed models can easily be adapted to this node version.

6 Conclusions

We presented a new approach to model PES problem using a propagation rule based on Ohm’s and Kirchoff’s laws to reduce the number of PMUs to place. We proposed two mathematical models: an iterative model and a bilevel one. The iterative model is based on the observability propagation process and is given by a binary linear program. The bilevel model is deduced from the iterative one using fixed point method. We showed that we can transform the bilevel model to a MILP. We proposed also an algorithm to solve the bilevel model. We implemented these models and algorithm for the bilevel program and we performed tests on different IEEE bus systems and randomly generated graphs. The results showed that: the iterative model cannot be used for medium and large instances; the MILP model can solve instances with more large size than the iterative one but cannot solve large size instances; and the bilevel algorithm can solve instances with large sizes. Therefore, the bilevel algorithm is better in terms of running time and size of instances that can be solved. Further future work could be to model the case of conventional measures. We can also consider the case of line outage and single contingency of PMUs. Another further future work would be to generalize our models for the case of PMUs with limited channels $\ell$. Also, due to maintenance or repairing works the electrical network topology is not fixed. Hence, another interesting perspective is to study the PMU placement problem under these conditions by proposing a robust model and a solution method to solve it.