# Lower Bounds for the Minimum Spanning Tree Cycle Intersection Problem

Manuel Dubinsky<EMAIL_ADDRESS>Kun-Mao Chao111Kun-Mao Chao was
supported in part by the Ministry of Science and Technology, Taiwan, under
grant number 111-2221-E-002-132-MY3. César Massri  Gabriel Taubin  Ingeniería
en Informática, Departamento de Tecnología y Administración, Universidad
Nacional de Avellaneda, Argentina  Departamento de Computación, Facultad de
Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Department of Computer Science and Information Engineering, National Taiwan
University, Taipei, Taiwan  Graduate Institute of Biomedical Electronics and
Bioinformatics, National Taiwan University, Taipei, Taiwan  Graduate Institute
of Networking and Multimedia, National Taiwan University, Taipei, Taiwan
Departamento de Matemática, Universidad de CAECE, CABA, Argentina  School of
Engineering, Brown University, Providence, RI, USA

###### Abstract

Minimum spanning trees are important tools in the analysis and design of
networks. Many practical applications require their computation, ranging from
biology and linguistics to economy and telecommunications. The set of cycles
of a network has a vector space structure. Given a spanning tree, the set of
non-tree edges defines cycles that determine a basis. The intersection of two
such cycles is the number of edges they have in common and the intersection
number -denoted $\cap(G)$-, is the number of non-empty pairwise intersections
of the cycles of the basis. The Minimum Spanning Tree Cycle Intersection
problem consists in finding a spanning tree such that the intersection number
is minimum. This problem is relevant in order to integrate discrete
differential forms. In this paper, we present two lower bounds of the
intersection number of an arbitrary connected graph $G=(V,E)$. In the first
part, we prove the following statement:

$\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right)\leq\cap(G),$

where $n=|V|$ and $\nu$ is the _cyclomatic number_ of $G$. In the second part,
based on some experimental results and a new observation, we conjecture the
following improved tight lower bound:

$(n-1)\binom{q}{2}+q\ r\leq\cap(G),$

where $2\nu=q(n-1)+r$ is the integer division of $2\nu$ and $n-1$. This is the
first result in a general context, that is for an arbitrary connected graph.

###### keywords:

Minimum spanning tree; Cycle intersection; Cycle basis; Intersection number

##  1 Introduction

Spanning trees play an important role in algorithm design [13]. The Minimum
Spanning Tree Cycle Intersection problem was proposed recently [6] as part of
a -still under development- mesh deformation algorithm in the context of the
field of Digital Geometry Processing [3]. More specifically, a _mesh_ is a
discretization of a surface represented as a graph embedded in 3D Euclidean
space. A _deformation_ is a consistent perturbation of the vertices of the
mesh to achieve some visual effect, which is relevant in simulations and 3D
animation.

The proposed deformation algorithm is based on interactively setting the
desired edge lengths globally or locally -in a region of the mesh-, and
automatically rearrange vertex positions in the best possible way to
approximate those lengths. Concretely, the situation can be expressed in these
terms: let $G=(V,E)$ be a directed connected graph and
$w:E\rightarrow\mathbb{R}$ be an edge function. We call $w$ a _discrete
1-form_ on $G$. Integrating $w$ is the problem of finding a vertex function
$x:V\rightarrow\mathbb{R}$ such that for every edge $e_{vw}=(v\rightarrow w)$,
the differential $dx:E\rightarrow\mathbb{R}$, defined as:
$dx(e_{vw}):=x(w)-x(v)$, approximates $w$ minimizing the error:

$\lambda(x)=\sum_{e_{vw}\in E}\left[dx(e_{vw})-w(e_{vw})\right]^{2}.$

The directed incidence matrix $D\in\\{0,1,-1\\}^{|E|\times|V|}$ of $G$ models
$dx$ in the sense that each row contains the information of an edge $e_{v,w}$:
-1 in the column of $v$, 1 in the column of $w$ and 0 otherwise. $D$ has rank
$n-1$, and its kernel is generated by $\bm{1}$ -the vector of all 1’s. This
degree of freedom can be explained by the fact that each translation of the
function $x$ (i.e.: $x+k$) has the same differential.

The set of cycles of a graph has a vector space structure over
$\mathbb{Z}_{2}$, in the case of undirected graphs, and over $\mathbb{Q}$, in
the case of directed graphs [9]. A basis of such a vector space is denoted
_cycle basis_ and its dimension is the _cyclomatic number_ $\nu=|E|-|V|+|CC|$
where $E$, $V$ and $CC$ are the set of edges, vertices and connected
components of the graph, resp. Given a cycle basis $B$ we can define its
_cycle matrix_ $\Gamma\in K^{|E|\times\nu}$ -where $K$ is the scalar field
(i.e.: $\mathbb{Z}_{2}$ or $\mathbb{Q}$)-, as the matrix that has the cycles
of $B$ as columns.

Let $G$ be a graph and $T$ a spanning tree of $G$. For an edge $e$ in $G-T$,
there is a cycle in $T\cup{e}$. We call those edges _cycle-edges_ and those
cycles _tree-cycles_. The set of tree-cycles of $T$ defines a cycle basis of
$G$.

The initial version of the mesh deformation algorithm consisted in choosing a
spanning tree $T$ of $G$ and solving the following linear system:

$M\begin{bmatrix}\bf\hat{x}\\\ \bf y\end{bmatrix}=\bf w,$

where $\bf\hat{x}\in\mathbb{R}^{\big{|}V\big{|}-1}$ is the solution of the
integration problem -fixing the value of and arbitrary vertex, in order to
eliminate the degree of freedom introduced by $dx$-, $\bf
y\in\mathbb{R}^{\nu}$ measures an error associated to each tree-cycle, $\bf
w\in\mathbb{R}^{\big{|}E\big{|}}$ is the evaluation of $w$ for every edge, and
$M$ is a matrix of this form:

$M=\left[\begin{array}[]{c|c}\hat{D}&\Gamma\end{array}\right],$

where $\hat{D}\in\\{0,1,-1\\}^{|E|\times|V|-1}$ is the directed incidence
matrix -without its first column-, and $\Gamma\in\\{0,1,-1\\}^{|E|\times\nu}$
is the cycle matrix induced by $T$. As the columns of $\hat{D}$ and $\Gamma$
generate orthogonal subspaces, $M$ has full rank and consquently the linear
system has a unique solution.

A natural question to consider is: how to choose $T$ such that its induced
cycle matrix $\Gamma$ is as sparse as possible, in order to apply fast linear
solvers. In more general terms, this is the formulation of the Minimum Cycle
Basis problem, defined independently by Stepanec [12] and Zykov [14], that can
be expressed as: given a connected graph, find a cycle basis such that the sum
of the length of its cycles is minimum. The variant of this problem where the
basis is induced by the cycles of a spanning tree is the Minimum Fundamental
Cycle Basis (MFCB) defined by Hubicka and Syslo [8]. A complete description of
this family of problems is developed by Kavitha et al. [9]. The computational
complexity of the MFCB problem belongs to the NP-Hard class [11]. Given this
computational restriction, we considered an equivalent version of the linear
system:

$M^{t}M\begin{bmatrix}\bf\hat{x}\\\ \bf y\end{bmatrix}=M^{t}\bf w.$

where the _Gram_ matrix $M^{t}M$ has the following form:

$M^{t}M=\left[\begin{array}[]{c|c}\hat{L}&0\\\
0&\hat{\Gamma}\end{array}\right]$

where $\hat{L}$ is the _Laplacian matrix_ of $G$ -without its first column-,
and $\hat{\Gamma}$ is the _cycle intersection matrix_ induced by $T$, that is:
a matrix in which the $ij$-entry contains the number of edges that the tree-
cycles $c_{i}$ and $c_{j}$ have in common. This matrix is interesting because
its blocks have good properties: there are fast solvers for Laplacian matrices
and $\hat{\Gamma}$ is -at least- symmetric, and it might have other good
properties.

In this context an equivalent natural question can be considered: how to
choose $T$ such that $\hat{\Gamma}$ is as sparse as possible. This motivated
us to formulate the Minimum Spanning Tree Cycle Intersection (MSTCI), which
can be expressed as: given a connected graph $G$, find a spanning tree $T$
such that the number of non-empty pairwise intersections of its tree-cycles is
minimum.

The MSTCI problem is not well studied yet, for example its complexity class is
unknown. One interesting result states that if $G$ contains a _universal
vertex_ -one that is connected to every other vertex-, then the _star spanning
tree_ is a solution [5]; in particular this can solve the case of dense
graphs: $|E|>(|V|^{2}-2|V|)/2$.

For a spanning tree $T$ of a connected graph $G$, the complement of the
sparsity of $\hat{\Gamma}$ can be measured by the intersection number w.r.t.
$T$, $\cap_{T}(G)$: the number of non-empty pairwise intersections between its
tree-cycles. Expressed in these terms, a solution of the MSTCI problem
minimizes this quantity which we call the intersection number of $G$, denoted
$\cap(G)$.

In this paper, we present two lower bounds of $\cap(G)$ of an arbitrary
connected graph $G$. This is relevant to measure the sparsity of
$\hat{\Gamma}$, and it is the first result in a general context.

The structure of the article is as follows. Section 2 sets notation,
convenient definitions and auxiliary results. Section 3 presents a proof of a
lower bound of the intersection number of a connected graph:

$\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right)\leq\cap(G),$

where $n=|V|$. In Section 4, an improved tight lower bound is conjectured
based on experimental results:

$(n-1)\binom{q}{2}+q\ r\leq\cap(G),$

where $2\nu=q(n-1)+r$ is the integer division of $2\nu$ and $n-1$. Finally,
Section 5 summarizes the conclusions.

##  2 Preliminaries

###  2.1 Notation

Let $G=(V,E)$ be a graph and $T$ a spanning tree of $G$. The number of
vertices and edges will be $|V|=n$ and $|E|=m$, resp. The number of cycles of
a cycle basis is $\nu=m-n+1$, known as the _cyclomatic number_ of $G$. The
unique path between $u,v\in V$ in the spanning tree $T$ is denoted $uTv$. The
degree of a vertex $v\in V$ will be denoted $d(v)$.

We will refer to the edges $e\in T$ as _tree-edges_ and to the edges in $G-T$
as _cycle-edges_. Every cycle-edge $e$ induces a cycle in $T\cup\\{e\\}$,
which we will call a _tree-cycle_. We will denote $\cap_{G}(T)$ to the number
of non-empty tree-cycle pairwise intersections w.r.t. $T$, being
$\cap(G)=\cap_{G}(T)$ the _intersection number_ of $G$ in the case where $T$
is a solution of the MSTCI problem.

A _universal vertex_ $u$ of $G$ is a vertex incident to all the other
vertices, i.e. $d(u)=n-1$. We shall call _star spanning tree_ to one that has
one vertex that connects to all other vertices -note that a universal vertex
induces a star spanning tree.$G$ is a _regular graph_ if all its vertices have
the same degree.

Finally, we will refer to the terms _vertex_ and _node_ interchangeably.

###  2.2 Auxiliary lemmas and definitions

In this section we present some auxiliary lemmas and definitions. In the
following, let $G=(V,E)$ be a connected graph and $T=(V,E^{\prime})$ a
spanning tree of $G$.

######  Definition 1.

[2] Let $e\in E^{\prime}$ be a tree-edge, and consider the two connected
components $T_{1}$ and $T_{2}$ determined by $T-\\{e\\}$. We define the _bond_
$b_{e}$ as the maximal set of edges $(v,w)\in E$ such that $v\in T_{1}$ and
$w\in T_{2}$.

######  Lemma 2.

Let $e\in E^{\prime}$ be an edge of $T$ and $b_{e}$ its corresponding bond.
Then, the edges in $b_{e}-\\{e\\}$ are cycle-edges that determine tree-cycles
that intersect pairwise.

###### Proof.

Let $T_{1},T_{2}$ be the two connected components determined by $T-\\{e\\}$,
and let $(v,w)\in b_{e}-\\{e\\}$. By definition, $v\in T_{1}$ and $w\in
T_{2}$, thus $vTw$ must contain $e$ and $vTw\cup(v,w)$ determines a tree-
cycle. This implies that $(v,w)$ is a cycle-edge and that the edges in
$b_{e}-\\{e\\}$ intersect pairwise. ∎

######  Lemma 3.

Let $f=(v,w)\in E-E^{\prime}$ be a cycle-edge. Then $f$ belongs to the bonds
corresponding to the edges of $vTw$.

###### Proof.

Let $e\in vTw$. Consider the two connected components $T_{1},T_{2}$ determined
by $T-\\{e\\}$. Clearly $v\in T_{1}$ and $w\in T_{2}$ then by definition $f\in
b_{e}$. ∎

######  Corollary 4.

Every cycle-edge belongs to at least two bonds.

###### Proof.

Let $f=(v,w)\in E-E^{\prime}$ be a cycle-edge. Since every cycle contains at
least three edges, it follows that $vTw$ has at least length two. By the
previous lemma the claim follows. ∎

Let $B_{T}=\\{b_{e}\\}_{e\in E^{\prime}}$ be the set of bonds w.r.t. $T$. Then
-by Lemma 2\- computing the total number of pairs of cycle-edges in $B_{T}$
overestimates $\cap_{G}(T)$:

$\sum_{e\in E^{\prime}}\binom{|b_{e}|-1}{2}\geq\cap_{G}(T).$

The overestimation is due to redundant intersections. Note that if the
intersection of two tree-cycles $c_{1},c_{2}$ contains two or more tree-edges,
then the corresponding pair of cycle-edges will be contained in more than one
bond. The next definition addresses this problem at the cost of incurring in
underestimation.

######  Definition 5.

Let $B_{T}=\\{b_{e}\\}_{e\in E^{\prime}}$ be the set of bonds w.r.t. $T$. Then
a _non-redundant bond set_ is a set $\hat{B}_{T}=\\{\hat{b}_{e}\\}_{e\in
E^{\prime}}$ such that:

  * 1.

$\hat{b}_{e}\subseteq b_{e}$

  * 2.

every edge $e\in E$ belongs to exactly one $\hat{b}_{e}$.

Note that as $E$ is finite, the bonds of $T$ and $B_{T}$ exist and are finite.
Thus in order to define a _non-redundant bond set_ $\hat{B}_{T}$, it suffices
to remove all but one occurrence of the duplicated edges in the bonds of
$B_{T}$.

######  Lemma 6.

If $T$ is a solution for the MSTCI problem w.r.t. $G$,
$\hat{B}_{T}=\\{\hat{b}_{e}\\}_{e\in E^{\prime}}$ a non-redundant bond set and
$\phi_{e}=|\hat{b}_{e}|-1$ for every $e\in E^{\prime}$, then

  * 1.

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

  * 2.

$\nu=\sum_{e\in E^{\prime}}\phi_{e}$.

###### Proof.

By Lemma 2 the edges in $\hat{b}_{e}-\\{e\\}$ are cycle-edges that intersect
pairwise. There are $\phi_{e}=|\hat{b}_{e}|-1$ cycle-edges in
$\hat{b}_{e}-\\{e\\}$, then $\hat{b}_{e}$ accounts for $\binom{\phi_{e}}{2}$
pairwise intersections. Since every edge belongs to exactly one _non-redundant
bond_ , every tree-cycle pairwise intersection is counted at most once, then
the first inequality holds. As each bond contains exactly $\phi_{e}$ cycle-
edges and every cycle-edge belongs to exactly one bond, the second equation
follows. ∎

The next Theorem clarifies the case of graphs that contain a universal vertex
in the context of the MSTCI problem.

######  Theorem 7.

[5] If a graph $G$ admits a star spanning tree $T_{s}$, then

$\cap_{G}(T_{s})\leq\cap_{G}(T)$

for any spanning tree $T$ of $G$.

######  Corollary 8.

[5] If a graph $G$ admits a star spanning tree $T_{s}$, then $T_{s}$ is a
solution of the MSTCI problem w.r.t. $G$.

######  Lemma 9.

[6] If $G$ is a graph that admits a star spanning $T_{s}$, then

$\cap(G)=\cap_{G}(T_{s})=\sum_{u\in V-\\{v\\}}\binom{d(u)-1}{2}.$

The next lemma is a well-known statement in convex optimization.

######  Lemma 10.

[4, §3.1.4] A quadratic function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$
defined as,

$f(x_{1},\dots,x_{n})=\bm{x}^{T}\bm{Q}\bm{x}+\bm{c}^{T}\bm{x}+d$

is strictly convex if and only if $Q$ is positive definite.

######  Lemma 11.

The matrix $M_{n}=\bm{I}+\bm{1}$ where $\bm{I}$ is the $n\times n$ identity
matrix and $\bm{1}$ is the $n\times n$ matrix whose entries are all equal to 1
is positive definite.

###### Proof.

As $\bm{1}$ has rank 1, then 0 is an eigenvalue with multiplicity $n-1$, and
the remaining eigenvalue is $tr(\bm{1})=n$, the trace of $\bm{1}$. So $\bm{1}$
is positive semidefinite. As $\bm{I}$ is positive definite, we conclude that
$M_{n}=\bm{I}+\bm{1}$ is positive definite. ∎

##  3 Proof of a lower bound

A lower bound of the intersection number seems interesting both in theoretical
and practical aspects. It gives an insight in the MSTCI problem, it can be
useful for comparing algorithms and as mentioned in the introduction, it can
approximate the sparsity of cycle intersection matrices. In this section we
present a proof of a lower bound.

######  Theorem 12.

If $G=(V,E)$ is a connected graph, then

$\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right)\leq\cap(G).$

###### Proof.

Let $T=(V,E^{\prime})$ be a solution of the MSTCI problem w.r.t. $G$, and
$\hat{B}_{T}=\\{\hat{b}_{e}\\}_{e\in E^{\prime}}$. a _non-redundant bond set_.
By Lemma 6, the following equations hold:

  1. 1.

$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G)$

  2. 2.

$\nu=\sum_{e\in E^{\prime}}\phi_{e}$,

where $\phi_{e}=|\hat{b}_{e}|-1$ for every $e\in E^{\prime}$. The expression
$\sum_{e\in E^{\prime}}\binom{\phi_{e}}{2}$ can be identified with a point in
the image of a function $f:\mathbb{R}^{n-1}\rightarrow\mathbb{R}$, defined as

$f(x_{1},\dots,x_{n-1})=\sum_{i=1}^{n-1}\binom{x_{i}}{2}=\sum_{i=1}^{n-1}\frac{x_{i}(x_{i}-1)}{2}.$

In this setting, in order to effectively calculate a lower bound of the
intersection number of $G$, the above expressions lead to the following
quadratic optimization problem [10, §9],

minimize $\displaystyle\quad\sum_{i=1}^{n-1}\binom{x_{i}}{2}$ subject to
$\displaystyle\quad\nu=\sum_{i=1}^{n-1}x_{i}.$

This minimization problem can be solved by restricting a degree of freedom of
the objective function, defining
$\hat{f}:\mathbb{R}^{n-2}\rightarrow\mathbb{R}$ as

$\hat{f}(x_{1},\dots,x_{n-2})=f(x_{1},\dots,x_{n-2},\nu-\sum_{i=1}^{n-2}x_{i}).$

The next step is to show that $\hat{f}$ is a strictly convex function and
consequently has a unique global minimum. The function $\hat{f}$ can be
expressed in matrix form as follows,

$\hat{f}(x_{1},\dots,x_{n-2})=\frac{1}{2}\left(\bm{x}^{T}(\bm{I}+\bm{1}^{n-2\times
n-2})\bm{x}-2\nu\bm{x}^{T}\bm{1}^{n-2}+\nu^{2}-\nu\right),$

where $\bm{x}=(x_{1},\dots,x_{n-2})^{T}$, $\bm{I}$ is the $(n-2)\times(n-2)$
identity matrix, $\bm{1}^{n-2\times n-2}$ and $\bm{1}^{n-2}$ are the
$(n-2)\times(n-2)$ matrix and the $n-2$ vector respectively, whose entries are
all equal to 1. By Lemma 10, $\hat{f}$ is strictly convex if and only if
$(\bm{I}+\bm{1}^{n-2\times n-2})$ is positive definite; this fact is proved in
Lemma 11. To calculate the unique minimum of $\hat{f}$ suffices to check where
its gradient vanishes,

$\nabla\hat{f}=(\bm{I}+\bm{1}^{n-2\times n-2})\bm{x}-\nu\bm{1}^{n-2}=0.$

The solution of this linear system is

$x_{i}=\frac{\nu}{n-1},\quad\forall\ 1\leq i\leq n-2$

and

$x_{n-1}=\nu-\sum_{i=1}^{n-2}x_{i}=\frac{\nu}{n-1}.$

The global minimum is

$\hat{f}\left(\frac{\nu}{n-1},\dots,\frac{\nu}{n-1}\right)=\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right).$

Summarizing, the following inequalities hold,

$\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right)\leq\sum_{e\in
E^{\prime}}\binom{\phi_{e}}{2}\leq\cap(G),$

and the global minimum of $\hat{f}$ is a lower bound of the intersection
number of $G$ as claimed. ∎

We will refer to the lower bound as

$l_{n,m}:=\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right).$

###  3.1 Evaluation

The next lemma focuses on the quality of $l_{n,m}$ in the sense that
quantifies its underestimation in a particular family of graphs.

######  Lemma 13.

If $G=(V,E)$ is a graph that contains a universal vertex $u\in V$ such that
the subgraph $G-\\{u\\}$ is $k$-regular with $k\geq 4$, then

$\frac{1}{8}\leq\frac{l_{n,m}}{\cap(G)}\leq\frac{1}{4}.$

###### Proof.

As $d(v)=k$ $\forall v\in V-\\{u\\}$, and the star spanning tree is a solution
of the MSTCI problem then according to the intersection number formula,

$\cap(G)=\sum_{v\in V-\\{u\\}}\binom{d(u)-1}{2}=\sum_{v\in
V-\\{u\\}}\binom{k-1}{2}=\frac{(n-1)(k-1)(k-2)}{2}.$

Taking into account that,

$m=\frac{1}{2}\sum_{v\in
V}d(v)=\frac{1}{2}\left((n-1)+(n-1)k\right)=\frac{(n-1)(k+1)}{2}.$

Then,

$\nu=m-(n-1)=\frac{(n-1)(k+1)}{2}-(n-1)=\frac{(n-1)(k-1)}{2}.$

Next, we analyze $l_{n,m}$,

$l_{n,m}=\frac{1}{2}\left(\frac{\nu^{2}}{n-1}-\nu\right)=\frac{(n-1)(k-1)(k-3)}{8},$

and finally we express the quotient,

$\frac{\frac{1}{2}(\frac{\nu^{2}}{n-1}-\nu)}{\cap(G)}=\frac{k-3}{4(k-2)}.$

This implies that when $k=4$ and $k\rightarrow\infty$, the lower and upper
bounds are met. ∎

This last result expresses two facts: 1) the underestimation of $l_{n,m}$ can
be considerable and 2) $l_{n,m}$ seems to perform better in dense graphs.

##  4 A conjectural tight lower bound

In this part, we conjecture an improved lower bound based on experimental
results. First we focus on graphs $G=(V,E)$ with a universal vertex $u\in V$.
Recall from Theorem 7 that the star spanning tree $T_{s}$ is a solution of the
MSTCI problem. Note that the sum of the degrees of the subgraph
$G^{\prime}=G-\\{u\\}$ verifies

$\sum_{v\in G^{\prime}}d(v)=2\nu.$

The following equivalent definitions refer to those graphs with a universal
vertex that minimizes the intersection number for a fixed number of vertices
and edges. The interpretation is simply the equidistribution of the total
degree among the remaining $n-1$ vertices.

######  Definition 14.

Let $G=(V,E)$ be a graph with a universal vertex $u\in V$ and $2\nu=q(n-1)+r$
the integer division of $2\nu$ and $n-1$. We shall say that $G$ is _$\nu$
-regular_ if the degree of every node $v\in V-\\{u\\}$ is $q+1$ or $q+2$.

######  Definition 15.

Let $G=(V,E)$ be a graph with a universal vertex $u\in V$ and $2\nu=q(n-1)+r$
the integer division of $2\nu$ and $n-1$. We shall say that $G$ is _$\nu$
-regular_ if it has exactly $n-1-r$ nodes with degree $q+1$ and $r$ nodes with
degree $q+2$.

The equivalence is based on the uniqueness of $q$ and $r$. Note that for every
$|V|=n$ and $|E|=m$ there are $\nu$-regular graphs, the proof can be expressed
by induction on $\nu$.

The following lemma shows that $\nu$-regular graphs minimize the intersection
number of graphs with a universal vertex.

######  Lemma 16.

If $G=(V_{G},E_{G})$ is a $\nu-regular$ graph and $H=(V_{H},E_{H})$ is a non
$\nu-regular$ graph with a universal vertex such that $|V_{G}|=|V_{H}|=n$ and
$|E_{G}|=|E_{H}|=m$, then

$\cap(G)<\cap(H).$

###### Proof.

Suppose on the contrary that $\cap(H)\leq\cap(G)$. Let $u_{H}$ be a universal
vertex of $H$. And -without loss of generality- let $H$ have a minimum
intersection number; more precisely let $J=(V_{J},E_{J})$ be a graph with a
universal vertex such that $|V_{J}|=n$ and $|E_{J}|=m$. Then the following
holds,

$\cap(H)\leq\cap(J).$

By definition as $H$ is not $\nu$-regular then a node with maximum degree and
a node with minimum degree $v_{max},v_{min}\in V_{H}-\\{u\\}$ satisfy that
$d_{H}(v_{max})-d_{H}(v_{min})>=2$. Let $(v_{max},w)\in E_{H}$ be an edge such
that $w\in V_{H}$ is not a neighbor of $v_{min}$. Consider the graph
$H^{\prime}=(V_{H},E_{H}-\\{(v_{max},w)\\}\cup\\{(v_{min},w)\\})$. According
to the hypothesis on $H$ and the formula presented in Lemma 9 the following
holds,

$\cap(H)=\sum_{v\in V_{H}-\\{u\\}}\binom{d_{H}(v)-1}{2}\leq\sum_{v\in
V_{H}-\\{u\\}}\binom{d_{H^{\prime}}(v)-1}{2}=\cap(H^{\prime}).$

As the degrees of all the nodes except for $v_{max}$ and $v_{min}$ coincide in
$H$ and $H^{\prime}$, the above inequality implies that,

$\binom{d_{H}(v_{max})-1}{2}+\binom{d_{H}(v_{min})-1}{2}\leq\binom{d_{H^{\prime}}(v_{max})-1}{2}+\binom{d_{H^{\prime}}(v_{min})-1}{2}.$

Let $d_{H}(v_{min})-1=k$ and $d_{H}(v_{max})-1=k+t$, rewriting the inequality
we have,

$\binom{k+t}{2}+\binom{k}{2}\leq\binom{k+t-1}{2}+\binom{k+1}{2}.$

Expanding the binomials,

$\frac{1}{2}[(k+t)(k+t-1)+k(k-1)]\leq\frac{1}{2}[(k+t-1)(k+t-2)+(k+1)k],$

which implies,

$(k+t-1)-k\leq 0\implies t\leq 1\implies d_{H}(v_{max})-d_{H}(v_{min})\leq 1.$

This contradicts the hypothesis on $H$ and consequently proves the lemma. ∎

Considering the general case of connected graphs -in an attempt to improve
$l_{n,m}$-, we decided to analyze those graphs that minimize the intersection
number for each fixed $n$ and $m$. The experiment consisted of exhaustively
checking the set of $7$ and $8$-node connected graphs. The interesting result
was that in this general setting, $\nu$-regular graphs also minimize the
intersection number; although not exclusively: in some cases there are other
graphs -without a universal vertex- that achieve the minimum intersection
number. We validated this fact by considering a sample of 1000 randomly
generated (by a uniform distribution) $9$-node connected graphs. This
evaluation resulted positive in all cases, and consequently enables to
formulate the following conjecture on a firm basis,

######  Conjecture 17.

Let $G$ be a $\nu-regular$ graph and $H$ be a connected graph such that
$|V(G)|=|V(H)|$ and $|E(G)|=|E(H)|$. Then

$\cap(G)\leq\cap(H).$

Based on the intersection number formula of Lemma 9, this conjecture implies
the following improved -and tight- lower bound of the intersection number.

######  Corollary 18.

If $G=(V,E)$ is a connected graph and $2\nu=q(n-1)+r$ the integer division of
$2\nu$ and $n-1$, then

$\hat{l}_{n,m}:=(n-1-r)\binom{q}{2}+r\binom{q+1}{2}=(n-1)\binom{q}{2}+q\
r\leq\cap(G).$

###  4.1 Comparison between $l_{n,m}$ and $\hat{l}_{n,m}$

Figure 1: Comparison of mean and standard deviation of
$\frac{\hat{l}_{n,m}}{\cap(G)}$ (blue) and $\frac{l_{n,m}}{\cap(G)}$ (red)
over a uniformly distributed random sample of size 1000 of $9$-node connected
graphs.

Figure 1 compares $\hat{l}_{n,m}$ and $l_{n,m}$ considering them as
proportions of $\cap(G)$ on a random sample of 9-node connected graphs. This
graphic suggests the following:

  * 1.

The performance improvement of $\hat{l}_{n,m}$ is much better than the one
expressed in Lemma LABEL:lemma:bound_comparison.

  * 2.

As the number of edges increases, $\hat{l}_{n,m}$ turns out be a tighter lower
bound of $\cap(G)$.

##  5 Conclusion

This article considers the Minimum Spanning Tree Cycle Intersection problem of
arbitrary connected graphs. In this general setting, we focused on two lower
bounds of the intersection number. The proof of the first lower bound
($l_{n,m}$) suggests two simple structural characteristics of the problem, a
solution to it should be the “best possible combination” of the following
conditions,

  * 1.

Tree-cycles should have short length so that each cycle-edge belongs to the
least number of bonds.

  * 2.

Cycle-edges should be equidistributed among bonds.

The first condition resembles the Minimum Fundamental Cycle Basis problem [9],
and the Low-stretch Spanning Tree problem [1, 7], whereas the second resembles
some form of average-cut. These similarities could be useful in order to
design algorithms.

The second tight lower bound ($\hat{l}_{n,n}$) is presented in a conjectural
form (Conjecture 17). It is based on so-called $\nu$-regular graphs. These
graphs verify the previous conditions and consequently reinforce their
importance. This last bound shows that graphs with a universal vertex play a
fundamental role, both because they are well understood cases and they provide
examples of minimum intersection number as a function of the number of nodes
and edges. The bound can be expressed in a very general context as follows.

_Let G=(V,E) be a connected graph and T a spanning tree of G. Then_

$(n-1)\binom{q}{2}+q\ r\leq\cap_{G}(T),$

_where $n=|V|$, $\nu$ is the cyclomatic number of G and $2\nu=q(n-1)+r$ is the
integer division of $2\nu$ and $n-1$._

As mentioned in the introduction, a solution of the MSTCI problem can be
useful for integrating discrete 1-forms on graphs. More specifically, fast
linear solvers can be applied to sparse linear systems that involve cycle
intersection matrices. We believe that this conjectured lower bound implies a
good approximation of the sparsity of those matrices for arbitrary connected
graphs. And this can help to decide if fast methods could be applied to linear
systems of large graphs.

## References

  * [1] Noga Alon, Richard M. Karp, David Peleg, and Douglas West, _A graph-theoretic game and its application to the k-server problem_ , SIAM Journal on Computing 24 (1995), no. 1, 78–100.
  * [2] J. A. Bondy and U. S. R. Murty, _Graph theory_ , Springer London, 2008.
  * [3] Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy, _Polygon mesh processing_ , A. K. Peters, 2010.
  * [4] Stephen Boyd and Lieven Vandenberghe, _Convex optimization_ , Cambridge University Press, Cambridge, England, March 2004.
  * [5] Min-Jen Chen and Kun-Mao Chao, _Proof of a conjecture about minimum spanning tree cycle intersection_ , Discrete Applied Mathematics 321 (2022), 19–23.
  * [6] Manuel Dubinsky, César Massri, and Gabriel Taubin, _Minimum spanning tree cycle intersection problem_ , Discrete Applied Mathematics 294 (2021), 152–166.
  * [7] Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng, _Lower-stretch spanning trees_ , SIAM Journal on Computing 38 (2008), no. 2, 608–628.
  * [8] E. Hubicka and M. M. Sysło, _Minimal bases of cycles of a graph_ , Recent advances in graph theory (1975), 283–293.
  * [9] Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, and Katharina A. Zweig, _Cycle bases in graphs characterization, algorithms, complexity, and applications_ , Computer Science Review 3 (2009), no. 4, 199–243.
  * [10] Katta G. Murty, _Optimization for decision making_ , International Series in Operations Research & Management Science, vol. 137, Springer, New York, 2010\. MR 3012844
  * [11] G. Prabhu Narsingh Deo, M. S. Krishnomoorthy, _Algorithms for generating fundamental cycles in a graph_ , ACM Trans. Math. Software 8 (1982), no. 1, 26–42.
  * [12] G. F. Stepanec, _Basis systems of vector cycles with extremal properties in graphs_ , Uspekhi Mat. Nauk 19 (1964), 171–175, in Russian.
  * [13] Bang Ye Wu and Kun-Mao Chao, _Spanning trees and optimization problems_ , CRC Press, 2004.
  * [14] A. A. Zykov, _Theory of finite graphs_ , Nauka, Novosibirsk, 1969, in Russian.


# Open Power System Data - Frictionless data for electricity system modelling

Frauke Wiese  Ingmar Schlecht<EMAIL_ADDRESS>Wolf-Dieter Bunke
Clemens Gerbaulet  Lion Hirth  Martin Jahn  Friedrich Kunz  Casimir Lorenz
Jonathan Mühlenpfordt  Juliane Reimann  Wolf-Peter Schill  Technical
University of Denmark, DTU Management Engineering, Produktionstorvet, Building
426, 2800 Kongens Lyngby, Denmark  University of Basel, Faculty of Business
and Economics, Peter Merian-Weg 6, 4052 Basel, Switzerland  Neon Neue
Energieökonomik GmbH (Neon), Karl-Marx-Platz 12, 12043 Berlin, Germany
Europa-Universität Flensburg, Energy and Environmental Management, Auf dem
Campus 1, 24943 Flensburg, Germany  Technische Universität Berlin, Straße des
17. Juni 135, 10236 Berlin, Germany  Hertie School of Governance,
Friedrichstraße 180, 10117 Berlin, Germany  Mercator Research Institute on
Global Commons and Climate Change, Torgauer Straße 12, 10829 Berlin  German
Institute for Economic Research (DIW Berlin), Mohrenstraße 58, 10117 Berlin,
Germany  TenneT TSO GmbH, Bernecker Straße 70, 95448 Bayreuth
Sachverständigen Rat für Umweltfragen, Luisenstraße 46, 10117 Berlin, Germany
Humboldt-Universität zu Berlin, School of Business and Economics, Spandauer
Straße 1, 10178 Berlin, Germany

###### Abstract

The quality of electricity system modelling heavily depends on the input data
used. Although a lot of data is publicly available, it is often dispersed,
tedious to process and partly contains errors. We argue that a central
provision of input data for modelling has the character of a public good: it
reduces overall societal costs for quantitative energy research as redundant
work is avoided, and it improves transparency and reproducibility in
electricity system modelling. This paper describes the Open Power System Data
platform that aims at realising the efficiency and quality gains of
centralised data provision by collecting, checking, processing, aggregating,
documenting and publishing data required by most modellers. We conclude that
the platform can provide substantial benefits to energy system analysis by
raising efficiency of data pre-processing, providing a method for making data
pre-processing for energy system modelling traceable, flexible and
reproducible and improving the quality of original data published by data
providers.

###### keywords:

electricity system modelling, frictionless data, data transparency, data
package, data platform, open data

††journal: Applied Energy

##  1 Introduction

Applied energy research as well as energy and climate policy advice are often
based on quantitative computer models [1, 2]. Activities in the field of
electricity system modelling [3, 4] have grown substantially over the last
years [5, 6]. This is, among other reasons, driven by increasing shares of
wind and solar power in many countries, and the desire to answer various
questions of integrating such variable renewable energy sources into power
systems and markets. For example, authors of this article have used European
electricity models to analyse the impact of renewable energy transitions on
various aspects of transmission networks, including congestion management [7],
country-specific grid issues [8], European long-term transmission scenarios
[9], merchant interconnectors [10] and unscheduled flows under market
splitting [11]. Other analyses have focused on wholesale prices [12], the
changing dispatch of thermal power plants [13], energy storage requirements
[14], interactions of investments in transmission, storage and thermal plants
[15], system effects of electric vehicles [16], or optimal configurations of
$100\%$ renewable electricity sectors and their respective transition pathways
[17].

Since many model-based analyses consider the conditions prevailing in today’s
power sectors as a starting point, current data is generally needed. While
many model applications differ with respect to data requirements — caused by
different model features and different geographical and temporal scopes —
input data on generation capacities as well as time series of load and
renewable power generation are relevant input parameters for the majority of
electricity system models. Several models also require hourly wholesale prices
as input parameters and for some weather data itself is an essential input.
The quality of such input data has a major influence on the scientific quality
of model-based studies and on their usefulness with respect to policy
conclusions.

Yet not only the quality of input data, but also its availability and
transparent application are essential for high-quality energy research. In
recent years, energy system modelling has been increasingly criticised for its
black box character in comparison to other fields [18]. The openness of code
and data are identified as key requirements for energy system models [19] to
comply with scientific standards like improved reproducibility and greater
scrutiny [20]. By allowing reuse and collaborative development, open models
and data can increase productivity and – through greater transparency [21] –
also increase credibility in the policy discourse [22]. Further, they allow
for public participation [17]. Since energy system models are highly relevant
for real-world policy advice on various aspects of renewable energy
transitions, the openness of data and models can also improve public trust and
credibility [23]. While open model code becomes more common [24] as proven by
the growing number of open models [25], transparency and openness of data is
still not widespread.

In general, the public availability of European electricity system data has
increased significantly during the last years due to rising transparency
regulation. An example of this has been the introduction of the ENTSO-E
Transparency Platform [26] (see [27] for a review). Yet, data is provided by
many different institutions and thus often dispersed over various repositories
and formatted in inconsistent ways. Further, data is often poorly documented
and sometimes includes obvious errors or missing values. In particular, there
are challenges related to:

  * 1.

the identification of appropriate sources

  * 2.

combinations of different data sources

  * 3.

manual downloads of multiple files

  * 4.

merging and harmonising different file formats and inconsistent formatting
within files

  * 5.

a lack of a standardised nomenclature and classification of energy sources and
technologies

  * 6.

poorly documented original data, in particular a lack of metadata

  * 7.

data quality (e.g inconsistencies, obvious errors, gaps in data)

Following [28], we summarise these issues as ”friction in the acquisition,
sharing, and reuse of research data”. Frictionless data, on the other hand,
should be easy to find and obtain, be provided in a standardised format and
nomenclature and be well documented and error-free.

The quality of such input data has a major influence on the scientific quality
of model-based studies and on their usefulness with respect to policy
conclusions. Although many models are used to generate insights, not numbers
[29], if the numbers that are fed into the model are neither correct nor well
documented, no reliable insights can be derived from a model at all. This
emphasises the importance for reliable data processing work-flows for the
whole energy system analysis.

Furthermore, the collection, processing, maintenance and verification of input
data imply substantial work loads for electricity system modellers. So far,
such activities are performed by many modelling teams in parallel, and
repeated regularly, whenever new data becomes available, i.e. each year or
even more frequently. It would clearly be much more efficient if these tasks
would be conducted in a collaborative and/or centralised manner. Likewise, the
quality of the processed data is likely to improve by knowledge sharing among
electricity system data users.

Thus, the originality of this paper consists in describing a data platform and
its underlying methodology, which aims to meet one of the most urgent needs of
energy system modellers: transparent, comprehensible and traceable data
processing. We provide a holistic method for this purpose, that can be applied
by each energy system modeller or community. Furthermore, we demonstrate that
the methods presented are actually applicable and well-working to deliver
crucial data for applied electricity system research.

Taking into consideration the relevance of input data for electricity system
modelling, the need for its transparency and the challenges arising from the
current situation, this article provides an overview of the project Open Power
System Data (OPSD), which aims at realising the efficiency and quality gains
for the modelling community. This is achieved by collecting, checking,
processing, aggregating, documenting and publishing data required for European
electricity system modelling on an online platform. OPSD was set up in the
context of a research project (first phase between 2015-2017) and is in its
second phase at the time of writing (2018-ongoing).

The concept and methods of OPSD are described in section 2, while section 3
explains the content and value added of the five OPSD data packages. We
conclude with a reflection on the current usage of the data platform as well
as possible extensions and remaining challenges (Section 4).

##  2 Design choices

To tackle the challenges outlined above, the authors created a central data
platform, OPSD [30], which provides the main input data used for power system
modelling at a central location in an aggregated and ready-to-download form.
OPSD is a free-of-charge data platform dedicated to electricity system
researchers. The data provided on the platform is collected from individual
sources, checked, processed, documented and published on the platform.

###  2.1 Definition of target group and scope

The idea behind OPSD is to avoid redundant work when collecting, preparing and
aggregating data for energy modelling. Thereby, the project is a service
provider to the modelling community. The target group of OPSD are energy
professionals such as modellers and analysts in academia, consulting firms and
industry. This choice of target group is instrumental in guiding the
conceptual decisions for the data platform. We focus on long historical time
series rather than high frequency updates of real-time information; and on
providing bare CSV files rather than visualisations of data.

The selection of data we provide is based on the data inputs common to most
electricity models as outlined in Section 1, namely time series data (solar,
wind, load and prices), individual as well as aggregated power plant data
(conventional and renewable) and weather data. We generally use data from
official sources such as from statistical authorities or transmission system
operators (TSOs) and only make careful and well-documented changes to the
original data.

###  2.2 Transparency improves quality and reliability

To allow for both scientific and policy-relevant use of the provided data, it
is crucial to ensure high quality, trustworthiness and reliability. The OPSD
concept was designed to meet these criteria. Besides choosing to only rely on
data from official sources, the main principle in this regard are open source
scripts, transparency of used input data and documentation of both the script
as well as the final output.

Along with each of our data packages, we provide the scripts that are used to
generate them. These scripts implement all steps including downloading of data
from the original sources, processing and reformatting and writing the final
output data for download on the OPSD platform. This not only enables data
users to read the script to see how the data was treated (such as finding out
which method to interpolate missing values was used), but also to take the
script and change parts of it in order to implement alternative data
processing steps at any point in the pipeline. Users can still benefit from
the remainder of the script to generate clean output data.

We put a special emphasis on documentation and chose a two-level approach
towards information about data on the platform. On a first level, for users
mainly interested in knowing what is to be found in the data files for
download, we provide a first short description of data contents along with
column-by-column documentation of individual data files directly on the
download page. For those who want to dive deeper and know exactly how the data
was treated, we use Jupyter notebooks, a format that combines script code and
documentation in a single file. The notebooks contain the most detailed
documentation of the provided data files and enable users to find out how the
data was sourced, treated and packaged up to the final product.

We refrain from making large-scale adjustments to the data in order to remain
close to the original sources. This enables data users to choose their
individual strategies to treat the data for their use case and trust in the
provided data to be close to original sources. However, we do make careful
modifications. These include the correction of obvious errors in the original
data such as GW-scale rooftop solar plants, alphabetical characters in
numerical data fields, missing commas, or aligning of different spellings for
the same categorical labels. To remain transparent to the data user about
modifications that were applied, a separate marker column marks each instance
where data was changed by OPSD.

A frequent problem with data in the power sector is that data that was once
available is removed from the original sources, or the location changes. We
tackle this problem on the one hand by making a copy of the original input
data available on our server next to the data package using it. On the other
hand, we try to do better on our side and keep historic versions of data
packages online under a stable and clear URL. This is complemented by stable
Digital Object Identifiers (DOIs) that we provide to enable referencing
individual versions of data packages.

While the majority of data packages on our platform are provided by the core
team behind OPSD, we also invite data contributions by third parties.
Contributions have to be relevant to our target audience, conform to the
technical standards (see Section 2.3) and be maintained for a prolonged time
period to be admitted to the platform.

###  2.3 Lightweight and scalable technical architecture

On all technical aspects of our platform, we aim at lightweight decentralised
solutions rather than complex centralised structures. We build on established
industry standards for open data (Data Packages), existing open-source
software solutions (Jupyter Notebooks and Python) and collaborative software
development tools (Git and GitHub).

The guiding principle by which we organise the data on our website comes from
the Data Package specification [31], a standard developed by Open Knowledge
International and the Frictionless Data project [28]. The standard is very
simple and relies on existing formats. It defines a Tabular Data Package to
consist of at least one comma-separated values (CSV) file and a text file
containing structured metadata in the JSON format.

The CSV file format allows for easy and fast download, as no database is
required on the server side. Furthermore, since CSV files are human-readable
and can be used by almost any software, they are a well-established format.
However, some variations of the standards exist, making usage not always
intuitive. We tackle this problem by following the Tabular Data Package
standard very strictly for our CSV files and by providing Excel and SQLite
files in addition.

Metadata is supplied in JSON files, which are both human-readable as well as
machine-readable and contain information about properties such as title of the
package, sources, contributors and the structure of the CSV files contained in
the data package. The machine readability of the metadata files allows users
of the data to automatically feed the data into their systems.

The scripts that we use to automatically download, process, and aggregate data
are written in Python. We use Jupyter Notebooks as a single file for coding
and documentation. A Jupyter Notebook is a documents that contains live code,
equations, visualisations and explanatory text. The notebooks created in this
project are available under the open-source MIT license on GitHub [32].

###  2.4 Central vs. decentral data preparation

Section 1 has highlighted a number of key issues with data for power system
modelling today, often being scattered across multiple sources, non-open and
time-consuming to process. Therefore, central data platforms, providing a
solution to these problems, are undoubtedly beneficial in regards to cutting
the time and cost involved in data preparation. However, centralisation of
data preparation also entails certain risks, which we outline and discuss
below, as they are crucial to the key choices made in creating the platform.

First, a major risk in central data provision concerns error propagation. A
single error in data preparation on the central data platform could propagate
into many studies based on the centrally provided data. We tackle this risk by
providing our scripts open source, so that others are invited to use and
scrutinise the scripts (which, according to the detailed feedback we get,
actually takes place). This makes error-detection easier than on closed-source
platforms, where users do not get to see the programming code. Furthermore, we
mark all instances where we intentionally modify and correct data, which
points users at the most critical data points to scrutinise.

Second, there might be a bias in data selection. While for some data sets many
competing sources are available (such as installed power plant capacity
figures being available from statistical offices, energy ministries and TSOs),
the data source selected by a central platform such as OPSD might be over-
represented in final data usage by scientists and analysts. We tackle this
issue by providing, where available, competing data sources so that users can
compare them against each other. This is especially the case for the national
generation capacity data package (see Section 3.4), but also concerns the time
series data package (see Section 3.5) regarding load values from two different
ENTSO-E sources.

Third, a central data platform might lead to a reduction of the plurality of
data preparation methods in use before. By centralising model data provision,
all users of the centrally provided data will base their studies on the
selected approaches instead of implementing their own methodologies in regard
to interpolation of missing values or detection of improbable data outliers,
which might lead to a bias if there are issues with the chosen treatment. We
address this issue by applying data modifications carefully only and in cases
where a correction is not possible and mark improbable data items, leaving it
to the user to do final modifications.

In summary, we argue that while there are risks from centralising data
preparation, these are to a large degree addressed by the design choices we
take.

###  2.5 Licensing

Ideally, the data available on OPSD would be provided under an open licence
such as those from the creative commons family. However, a prerequisite for
granting an open license would be that the providers of original data sources
gave their permission or were themselves using open licenses, which is hardly
the case (exceptions are Danish and French TSOs Energinet.dk [33] and RTE
[34]). We have sent enquiries to data providers asking to republish their data
under the Creative Commons Attribution 4.0 International license. While some
providers granted their permission, others refrained or did not reply.
Singling out and licensing the data from providers who gave permission would
be possible, but highly impractical, which is why we decided against it.

###  2.6 Maintenance and longevity

All too often with the end of funding for an academic project also the outputs
it provides fade. Therefore, we have tackled the issue of long-term
maintenance and future updates in our design choices already.

Three design choices we made are instrumental in promoting longevity. Firstly,
by doing our data preparation script-based and providing those scripts as open
source, we make it very easy for others to continue on from the state we might
ever leave the project in, in the unlikely case that we do not manage to
secure a continuation beyond 2020. The choice of an open-source license also
makes transitioning of the whole OPSD project to other institutions possible,
as no intellectual property rights stand in the way. Secondly, by choosing a
lightweight and decentralised IT approach that requires only a very basic and
cheap shared-hosting environment, we keep the hosting costs below the price of
a cup of coffee per month, enabling us to make long-term commitments to keep
hosting alive. Thirdly, by choosing to provide Digital Object Identifiers
(DOIs) for our data packages, we were obliged to sign a contract with the DOI
issuer and commit to a long-term availability of the provided data. This also
helps us to signal the stability and longevity we strive for to the users of
our platform.

##  3 Five data packages

###  3.1 Overview

For the illustration of our work on and methods for tackling the challenges of
input data for electricity system modelling, we describe scope, coverage and
value added for each of the five currently available OPSD data packages. These
cover a large share of input data required by electricity system models:

  * 1.

Conventional power plants – Lists of conventional power plants and units

  * 2.

Renewable power plants – Lists of renewable energy power stations

  * 3.

National generation capacity – An overview of generation capacities by
technology and country from different original sources

  * 4.

Time series – Load, wind, solar, and price data in hourly resolution

  * 5.

Weather data – Hourly geographically aggregated weather data for Europe

Due to a varying availability of original data, the geographical as well as
the temporal coverage of the resulting data packages differ. Therefore, an
overview of coverage is provided in the data availability matrix (Figure 1).
Countries covered in the different data packages are indicated by blue
coloured cells. The cell content further specifies the earliest year of
availability (time series) or the type of power plants covered (renewable and
conventional).

Figure 1: Overview of the current data availability (as of May 2018).

A time-consuming barrier for input data handling from different sources are
divergent naming conventions and classifications from different original data
sources. Thus, an essential contribution of OPSD for smoother input data
handling and better comparability of original data is a consistent
classification of energy sources and technologies (see Figure 2) which we
consistently apply to the data packages where this is relevant, i.e. the first
three in the list above. On the first level, we generally distinguish between
renewable energy sources, fossil fuels, nuclear and other or unspecified
sources. The second level contains different renewable sources such as wind
and solar power as well as different fossil fuels. The third level is
necessary to distinguish between different forms of bio energy.

Figure 2: Classification of energy sources and technologies

In the following, we describe the content, scope and particular features of
each data package. Please note that only the most relevant of the large amount
of original data sources are mentioned while a full list can be found on the
OPSD platform itself [30].

###  3.2 Conventional power plants

#### Content and Scope

This package contains data on conventional power plants for Germany and
selected other European countries. It covers nuclear reactors and thermal
plants fuelled by lignite, hard coal, natural gas or oil, as well as hydro
power and pumped hydro storage. The package focuses on individual power
plants, or power plant blocks, and their technical characteristics. These
include installed capacity, main energy source and type of technology. Where
available, we also include capabilities with respect to combined heat and
power (CHP) generation, commissioning and closure years as well as
geographical information and Energy Identification Codes (EIC). We also
provide information on thermal efficiency of individual plants, either by
means of desk research or based on an estimation method described in [35].

The main data source for Germany is a detailed power plant list provided by
the federal network regulator (BNetzA [36]). It is complemented with a list
provided by the German Environment Agency (UBA [37]) which contains additional
information on CHP, installed gross capacities, and turbine types. Sources for
other countries include detailed power plant lists provided by TSOs,
ministries, or associations and market participants. For countries without
system-wide power plant lists the lists have been manually combined from
multiple official sources.

While we implemented a single data structure for all countries covered, the
package consists of two separate Jupyter Notebooks and two separate output
files: one for Germany and one for the other countries. This is because the
original German data provides many more details compared to the other
countries, and also requires a specific merging activity of the lists provided
by BNetzA and UBA.

#### Geographic coverage

Geographically, the data package focuses on Germany and its neighbouring
countries. The data package currently covers Austria, Belgium, the Czech
Republic, Denmark, Germany, Finland, France, Italy, the Netherlands, Norway,
Poland, Spain, Sweden, Switzerland, Slovakia, Slovenia, and the United
Kingdom. Due to varying availability and quality of original data, not all
information is available for each country.

#### Value added

This data package is designed to benefit electricity system modellers in
several ways. First, we provide a single data structure for many countries,
including a harmonisation of fuels and technologies, the latter sometimes
inferred from other information provided in the original data or based on own
assessments. Specifically for Germany, merging the two official lists provided
by BNetzA and UBA adds value with respect to CHP information, net / gross
capacities, as well as commissioning and shut-down years. Further,
complementary information which is not included in the primary sources but
researched manually, i.e., geo coordinates, EIC codes, and thermal efficiency,
should be of use for many modellers.

###  3.3 Renewable power plants

#### Content and Scope

This data package contains a list of existing solar, wind, bio, run-of-river,
geothermal and other renewable power plants. Due to different data and
parameter availability in the countries, one list is provided per country.
These are of different accuracy and partly include different parameters.
However, all lists state energy source and technology, electrical capacity and
data source. If available in the original data, the respective system
operators (transmission and distribution), support scheme ID or technology-
specific parameters like hub height for wind turbines are included. While a
high amount of parameters and units (more than 1.8 million power plant
entries) are available for Germany, these only cover plants eligible under the
renewable support scheme (EEG). Also for Switzerland just the supported plants
are provided (Swiss feed-in tariff KEV) since these are well documented and
information is publicly provided. For Denmark, detailed data on solar and wind
power plants including rotor diameter etc. is provided, but no other
technologies. Aggregated capacity per energy source and municipality is stated
in the lists for Poland and France.

Most original data sources either provide conventional or renewable power
plants. However, especially with respect to hydro power, there is an overlap
between sources, and harmonisation is challenging. In Germany, in the last
decades, several data providers (four TSOs and the federal agency BNetzA)
report differently on hydro power plants depending on various laws, regulation
and publication requirements. Combining different sources partly leads to
double-counting of hydro power plants in renewable and conventional power
plant lists, due to inconsistent statistic counting methods. With the
objective to provide data packages that can be directly applied by the
modellers, we eliminated the overlap to some extent by clarifying which energy
sources and which technologies are covered by the conventional and renewable
data package as illustrated in Figure 2.

#### Geographic coverage

Currently, lists of German, Danish, Swiss, Polish and French renewable power
plants are provided. Since the location of renewable power plants is important
for resulting feed-in of wind and solar, the geographic location is provided
wherever information was available. This is the case for Germany, Denmark and
France. These coordinates are of different accuracy depending on the original
source being derived from coordinates in UTM-format (BNetzA), zip-codes
(German TSOs) or districts.

#### Value added

The amount of renewable energy units by far exceed the conventional ones due
to smaller unit size, which makes processing tedious and manual verification
on a unit-by-unit base impossible. Furthermore, naming conventions and
classification of renewable energy technologies and sources differ
significantly between data providers. The added value of the script is thus
bringing it to the same energy source structure as well as to the same
formatting. Although some parameters differ between the country scripts, the
country lists can be consistently combined for a subset of essential
parameters. Furthermore, inconsistent data points (like e.g. rooftop solar
installations of several GW) are marked and can thus easily be filtered out.

An additional output of this data package and value added are historic daily
time series of the installed renewable capacities per energy source type for
Germany. These are applied in the time series script: Since solar and wind
feed-in time series are derived from real feed-in data, feed-in levels tend to
increase over the year due to increasing installed capacity. For deriving
relative, normalised hourly profiles, the corresponding installed capacity of
the respective day is required. The creation of this output requires the date
of installation from the original data source and is thus only provided for
those countries for which this information is available. Until November 2018,
this is only the case for Germany.

###  3.4 National generation capacity

#### Content and Scope

This data package complements the Conventional power plants and Renewable
power plants packages by providing aggregated numbers on installed capacities
for all types of generators. To create this package, we compiled a broad range
of sources and structured them according to the harmonised classification of
energy sources and technologies provided in Figure 2. This proved to be
challenging because of very heterogeneous reporting conventions across
national statistics. Overall, we provide more than $1500$ annual country
statistics from four international and $25$ national sources, i.e. around four
statistics for each country covering several years each. As for the
international sources, we use data provided by ENTSO-E and EUROSTAT, the
latter going back to 1990. National data sources include statistical offices,
ministries, TSOs and industry associations. While the international sources
are automatically processed, the national sources generally require manual
compilation.

#### Geographic coverage

The package provides data on 39 countries and thus virtually comprises all
European countries. 25 of these countries are not only covered by
international sources, but also complemented by individual country statistics.
For example, 2015 data for France comprises four distinct data sources.

#### Value added

The main output of this package is a single data file that includes installed
generation capacities for all European countries, with a harmonised coverage
of energy sources and generation technologies. This is valuable for all
electricity system models that do not require much technological or geographic
detail, for example linear models that consider whole countries as nodes.
Additional value is created by contrasting different sources for a given
country and year, located in adjacent columns of the data file. This enables
the user, inter alia, to draw conclusions on the quality and coverage of
specific sources or to infer missing values. For example, overall generation
capacity installed in France in 2015 varies between $105$GW and $129$GW across
the different sources, with particularly large variation among renewable
sources.

To name another benefit, the temporal and geographical coverage of this
package is much better compared to the other two data packages covering
conventional and renewable generators. Not least, we also provide a strict
distinction between values that are actually zero and such that are not
available or not specified in national / international statistics.

###  3.5 Time series

#### Content and Scope

The Time series data package contains highly granular time series data for a
number of parameters. Included are power consumption (load), day-ahead power
prices, as well as three types of time series related to generation by
variable renewables (wind and solar). The wind and solar time series include
historical forecast generation, actual generation and installed production
capacity. The latter is calculated from the Renewable power plants package and
is required to calculate renewable generation profiles as share of installed
production capacity.

Depending on the national market set-up, the time series have a resolution of
either 15 minutes (i.e. Austria, Germany and some neighbours), 30 minutes
(i.e. the British Isles) or 60 minutes (all other countries).

While from 2015 onward, many of the data are available from the ENTSO-E
Transparency Platform, earlier records have to be obtained through individual
national sources. Data are extracted mostly from national TSO’s websites,
ENTSO-E’s ”Monthly statistics data collection” as well as ENTSO-E
Transparency.

Many original data sources report data by referring to the local time, in most
cases Central European (Summer) Time (CET/CEST). Transitions between summer
daylight saving time and winter time are a source of confusion, since they
imply jumping an hour in March and reporting an hour twice in October. We thus
consistently convert all time stamps to Coordinated Universal Time (UTC),
which avoids daylight saving time.

Since power system modelling usually requires time series data to be complete
for at least an entire year, data gaps of up to two hours are filled by
applying linear interpolation. In these cases, tables are annotated with a
marker, allowing users to trace back original data manipulation, while longer
periods of missing data are left as-is.

#### Geographic coverage

Overall, 35 countries are covered while varying between parameters and
improving in more recent years. While load data is published for all European
countries, availability of renewable generation data varies between countries.
Historic records of day-ahead prices are freely available since 2015, when the
ENTSO-E Transparency Platform was introduced.

#### Value added

This package relieves researchers of the burden to collect time series data
from many different sources, each using different formats and ways to organise
data: Some TSOs allow downloading one file containing all available data
(Amprion), while others require downloading and combining monthly (TenneT) or
even daily files (PSE). The time series data package combines all data with
the same temporal resolution in one file each, facilitating its use for
modellers. Additionally, 15 and 30 minutes data are aggregated to hourly time
series since this is the resolution required by most power system models and
enables one file with maximal geographic coverage while keeping the file size
manageable.

###  3.6 Weather data

#### Content and Scope

The Weather data package provides a script to automatically access, subset,
download and process wind, solar, temperature and air data based on the
MERRA-2 dataset [38, 39] made available by NASA. This data package differs
significantly from the other data packages as the size of the data to be
downloaded can reach GB and TB if a large amount of parameters, a long time
span and a huge geographical area are chosen. Thus, instead of offering the
download of ready-made data packages, the strategy here is to provide a
documented methodological Python script that can be run on the user’s
computer. This script serves as a documented tutorial and enables the user to
specify the geographical area and the time span for which the data shall be
downloaded and processed. Only a small sample data set (Germany, 2016) is
available for direct download.

Besides connection to the database, download and conversion of the three-
dimensional NetCDF4-format to CSV and SQL-output, the script includes the
calculation of the input parameters relevant for electricity system modellers.
For example, the wind speed is calculated from the north and east pointing
wind vectors provided in the original MERRA-2 data set. Resulting parameters
covered by the script are:

  * 1.

wind velocity in 2, 10 and 50 meters height as well as roughness length

  * 2.

solar radiation

  * 3.

temperature

  * 4.

air density and pressure

#### Geographic coverage

The MERRA-2 data set offers reanalysis data with a worldwide coverage in a
resolution of 0.625∘ x 0.5∘ which correlates to approximately 50 x 50 km in
Central European latitudes. By specifying the northeastern and southwestern
corner coordinates in the script, a rectangular area can be chosen.

#### Value added

Due to the rising influence of wind and solar feed-in for the power system,
their realistic representation and thus weather parameters are crucial for
electricity system models. The OPSD weather data script fills a gap between
original meteorological data and ready-made feed-in time series. On the one
end of the spectrum, the direct usage of original data sets like MERRA-2 with
hundreds of different weather parameters to choose from as well as a tedious
manual download and processing requires specific knowledge to retrieve the
relevant data for electricity system modelling. Additionally, the NetCDF-file
format preferred by meteorologist due to its multidimensional structure is
hard to handle and not directly compatible with data formats preferred by
energy system modellers. On the other end, ready-made feed-in time series as
provided in the data package described in Section 3.5 are less flexible for
the automatic adaption to own modelling code and are restricted by fixed
assumptions made for the calculation of the resulting electricity feed-in,
e.g. the hub height or type of wind turbines. Using CSV instead of original
NetCDF-files implies the downside of less efficiency in terms of organising
and storing the data. But since this is a major limitation for electricity
system modellers who require decades of historical weather data, and who carry
out own feed-in calculations, the OPSD script lowers the barrier of utilising
the wealth of available reanalysis weather data by making them more accessible
in CSV-format.

##  4 Discussion and Outlook

The OPSD platform has been designed to provide a service to the electricity
system modelling community. It provides a wide range of data at one place, is
easily accessible, clean and ready-to-use, permanently available and version-
controlled. The large number of users — around $100,000$ unique visitors
during 2017) — and, more importantly, the amount of research that makes use of
OPSD — 26 published papers by the time of writing since the go-live in late
2016, out of which 12 are published papers in high quality journals indexed in
the SCI/SSCI [40, 41, 42, 43, 44, 45, 13, 46, 47, 48, 49, 50] and 14 in other
journals, conference papers, books and grey literature [51, 52, 53, 54, 55,
56, 57, 58, 59, 60, 61, 62, 63, 64] — suggest that the platform fulfils a need
and provides value to electricity system modellers.

The main contribution of this paper is to provide a systematic overview of the
OPSD platform and its main methodological approaches. This platform addresses
a big challenge for energy system modellers: to process and document massive
amounts of input data from various sources in a flexible, but still
reproducible way. It thus helps to overcome one of the main barriers to
improving transparency in modelling, which researchers have urgently called
for [19].

Clearly, there is room for improvement. Planned future work includes expanding
the geographic scope of the platform, adding additional data items, and
improving usability.

An ongoing challenge for projects like OPSD is the academic incentive
structure. Collecting, cleaning, aggregating and providing data is essential,
everyone agrees. However, it is challenging to attract funding for these kinds
of projects and even more difficult to publish journal articles on data
processing and aggregation. As a consequence, open data, like many other
public goods, tends to remain short in supply.

In the long term, we hope that OPSD provides additional benefits by serving as
a proof of concept. It may help to convince the providers of data –– system
operators, statistical offices, generation companies, and public authorities
–– to provide data that is complete and can be easily used for research. With
machine-readable data and metadata that is packaged and version-controlled,
along with quality and consistency checks and detailed data documentation, the
electricity sector would make a huge step towards frictionless data.

## Acknowledgements

The OPSD project has been supported by the German Federal Ministry for
Economic Affairs and Energy (BMWi) in its first phase 2015-2017 under grant
number 03MAP324. Since 2018, it is maintained and amended as part of the
project ”Open Source Energiewende” (060/17) for BMWi. The authors also thank
all colleagues contributing to the platform, the open energy modelling
initiative and all users of OPSD providing feedback.

## References

## References

  * [1] S. Pfenninger, A. Hawkes, J. Keirstead, Energy systems modeling for twenty-first century energy challenges, Renewable and Sustainable Energy Reviews 33 (2014) 74–86.  doi:10.1016/j.rser.2014.02.003.
  * [2] J. DeCarolis, H. Daly, P. Dodds, I. Keppo, F. Li, W. McDowall, S. Pye, N. Strachan, E. Trutnevyte, W. Usher, M. Winning, S. Yeh, M. Zeyringer, Formalizing best practice for energy system optimization modelling, Applied Energy 194 (2017) 184–198.  doi:10.1016/j.apenergy.2017.03.001.
  * [3] D. Connolly, H. Lund, B. Mathiesen, M. Leahy, A review of computer tools for analysing the integration of renewable energy into various energy systems, Applied Energy 87 (4) (2010) 1059–1082.  doi:10.1016/j.apenergy.2009.09.026.
  * [4] H. K. Ringkjøb, P. M. Haugan, I. M. Solbrekke, A review of modelling tools for energy and electricity systems with large shares of variable renewables, Renewable and Sustainable Energy Reviews 96 (2018) 440–459.  doi:10.1016/j.rser.2018.08.002.
  * [5] L. M. Hall, A. R. Buckley, A review of energy systems models in the UK: Prevalent usage and categorisation, Applied Energy 169 (2016) 607–628.  doi:10.1016/j.apenergy.2016.02.044.
  * [6] R. Fernandez Blanco Carramolino, F. Careri, K. Kavvadias, I. Hidalgo Gonzalez, A. Zucker, E. Peteves, Systematic mapping of power system models, Tech. rep. (2017).  doi:10.2760/422399.
  * [7] F. Kunz, Improving Congestion Management: How to Facilitate the Integration of Renewable Generation in Germany, The Energy Journal 34 (4) (2013) 55–78.  doi:10.5547/01956574.34.4.4.
  * [8] I. Schlecht, H. Weigt, Linking Europe: The Role of the Swiss Electricity Transmission Grid until 2050, Swiss Journal of Economics and Statistics 151 (2) (2015) 125–165.  doi:10.1007/BF03399415.
  * [9] J. Egerer, C. Gerbaulet, C. Lorenz, European electricity grid infrastructure expansion in a 2050 context, The Energy Journal 37 (1) (2016) 101–124.  doi:10.5547/01956574.37.SI3.jege.
  * [10] C. Gerbaulet, A. Weber, When regulators do not agree: Are merchant interconnectors an option? Insights from an analysis of options for network expansion in the Baltic Sea region, Energy Policy 117 (2018) 228–246.  doi:10.1016/j.enpol.2018.02.016.
  * [11] F. Kunz, Quo Vadis? (Un)scheduled electricity flows under market splitting and network extension in central Europe, Energy Policy 116 (2018) 198–209.  doi:10.1016/j.enpol.2018.01.051.
  * [12] L. Hirth, What caused the drop in European electricity prices? A factor decomposition analysis, The Energy Journal 39 (1) (2018) 143–157.  doi:10.5547/01956574.39.1.lhir.
  * [13] W.-P. Schill, M. Pahle, C. Gambardella, Start-up costs of thermal power plants in markets with increasing shares of variable renewable generation, Nature Energy 2 (17050) (2017) .  doi:10.1038/nenergy.2017.50.
  * [14] W.-P. Schill, A. Zerrahn, Long-run power storage requirements for high shares of renewables: Results and sensitivities, Renewable and Sustainable Energy Reviews 83 (2018) 156–171.  doi:10.1016/j.rser.2017.05.205.
  * [15] J. Egerer, W.-P. Schill, Power system transformation toward renewables: Investment scenarios for Germany, Economics of Energy & Environmental Policy 3 (2) (2014) 29–44.  doi:10.5547/2160-5890.3.2.jege.
  * [16] W.-P. Schill, C. Gerbaulet, Power system impacts of electric vehicles in Germany: Charging with coal or renewables?, Applied Energy 156 (2015) 185–196.  doi:10.1016/j.apenergy.2015.07.012.
  * [17] F. Wiese, G. Bökenkamp, C. Wingenbach, O. Hohmeyer, An open source energy system simulation model as an instrument for public participation in the development of strategies for a sustainable future, WIREs Energy Environ 3 (5) (2014) 490–504.  doi:10.1002/wene.109.
  * [18] S. Pfenninger, J. DeCarolis, L. Hirth, S. Quoilin, I. Staffell, The importance of open data and software: Is energy research lagging behind?, Energy Policy 101 (2017) 211–215.  doi:10.1016/j.enpol.2016.11.046.
  * [19] S. Pfenninger, L. Hirth, I. Schlecht, E. Schmid, F. Wiese, T. Brown, C. Davis, M. Gidden, H. Heinrichs, C. Heuberger, S. Hilpert, U. Krien, C. Matke, A. Nebel, R. Morrison, B. Müller, G. Pleßmann, M. Reeg, J. C. Richstein, A. Shivakumar, I. Staffell, T. Tröndle, C. Wingenbach, Opening the black box of energy modelling: Strategies and lessons learned, Energy Strategy Reviews 19 (2018) 63–71.  doi:10.1016/j.esr.2017.12.002.
  * [20] F. Wiese, S. Hilpert, C. Kaldemeyer, G. Pleßmann, A qualitative evaluation approach for energy system modelling frameworks, Energy, Sustainability and Society 8 (1) (2018) .  doi:10.1186/s13705-018-0154-3.
  * [21] K.-K. Cao, F. Cebulla, J. J. Gómez Vilchez, B. Mousavi, S. Prehofer, Raising awareness in model-based energy scenario studies – a transparency checklist, Energy, Sustainability and Society 6 (28) (2016) .  doi:10.1186/s13705-016-0090-z.
  * [22] C. Dieckhoff, A. Eberspächer, Consulting with energy scenarios - Requirements for scientific policy advice, Accessed 24 June 2016 (2016).
URL
http://www.akademienunion.de/fileadmin/redaktion/user_upload/Publikationen/Stellungnahmen/Stellungnahme_Energy_scenarios.pdf

  * [23] S. Pfenninger, Energy scientists must show their workings, Nature 542 (2017) 393\.  doi:doi:10.1038/542393a.
  * [24] R. Morrison, Energy system modeling: Public transparency, scientific reproducibility, and open development, Energy Strategy Reviews 20 (2018) 49–63.  doi:10.1016/j.esr.2017.12.010.
  * [25] Opemod Initiative (open energy modelling initiative), Open Models, Accessed 29 May 2018.
URL http://wiki.openmod-initiative.org/wiki/Open_Models

  * [26] European Network of Transmission System Operators for Electricity (ENTSO-E), ENTSO-E Transparency Platform (2018).
URL https://transparency.entsoe.eu

  * [27] L. Hirth, J. Mühlenpfordt, M. Bulkeley, The ENTSO-E Transparency Platform –- A review of Europe’s most ambitious electricity data platform, Applied Energy 225 (2018) 1054–1067.  doi:10.1016/j.apenergy.2018.04.048.
  * [28] D. Fowler, J. Barratt, P. Walsh, Frictionless data: making research data quality visible, International Journal of Digital Curation 12 (2) (2017) 274––285.  doi:10.2218/ijdc.v12i2.577.
  * [29] H. G. Huntington, J. P. Weyant, J. L. Sweeney, Modeling for insights, not numbers: the experiences of the energy modeling forum, Omega 10 (5) (1982) 449 – 462.  doi:10.1016/0305-0483(82)90002-0.
  * [30] Open Power System Data - A free and open data platform for power system modelling. (2018).
URL https://open-power-system-data.org/

  * [31] Open Knowledge International, Frictionless Data Specifications and Software: Data Package.
URL https://frictionlessdata.io/specs/data-package/

  * [32] Open Power System Data - Repositories on github (2018).
URL https://github.com/Open-Power-System-Data

  * [33] Energinet.dk, Energi data service (2018).
URL https://www.energidataservice.dk/

  * [34] RTE, GRTgaz, Teréga, AFGNV, Storengy, Dunkerque LNG, Elengy, Weathernews, Open Data Réseaux Énergies (ODRÉ) (2018).
URL https://opendata.reseaux-energies.fr

  * [35] J. Egerer, C. Gerbaulet, R. Ihlenburg, F. Kunz, B. Reinhard, C. von Hirschhausen, A. Weber, J. Weibezahn, Electricity sector data for policy-relevant modeling: Data documentation and applications to the German and European electricity markets, Tech. rep., Data Documentation, DIW (2014).
URL
http://www.diw.de/documents/publikationen/73/diw_01.c.440963.de/diw_datadoc_2014-072.pdf

  * [36] Bundesnetzagentur (German Federal Network Agency), Power Plant List (in German) (2018).
URL
https://www.bundesnetzagentur.de/EN/Areas/Energy/Companies/SecurityOfSupply/GeneratingCapacity/PowerPlantList/PubliPowerPlantList_node.html

  * [37] Umweltbundesamt (German Federal Environment Agency), Database ”Power plants in Germany” (in German, Datenbank ”Kraftwerke in Deutschland”) (2018).
URL https://www.umweltbundesamt.de/dokument/datenbank-kraftwerke-in-
deutschland

  * [38] Global Modeling and Assimilation Office (GMAO) at NASA Goddard Space Flight Center, Modern-Era Retrospective Analysis for Research and Applications, version 2.
URL https://gmao.gsfc.nasa.gov/reanalysis/MERRA-2/

  * [39] M. M. Rienecker, M. J. Suarez, R. Gelaro, R. Todling, J. Bacmeister, E. Liu, M. G. Bosilovich, S. D. Schubert, L. Takacs, G.-K. Kim, S. Bloom, J. Chen, D. Collins, A. Conaty, A. da Silva, W. Gu, J. Joiner, R. D. Koster, R. Lucchesi, A. Molod, T. Owens, S. Pawson, P. Pegion, C. R. Redder, R. Reichle, F. R. Robertson, A. G. Ruddick, M. Sienkiewicz, J. Woollen, MERRA: NASAs Modern-Era Retrospective Analysis for Research and Applications, Journal of Climate 24 (14) (2011) 3624–3648.  doi:10.1175/JCLI-D-11-00015.1.
  * [40] M. Klein, M. Deissenroth, When do households invest in solar photovoltaics? An application of prospect theory, Energy Policy 109 (2017) 270–278.  doi:10.1016/j.enpol.2017.06.067.
  * [41] N. H. El-Amary, A. Balbaa, R. A. Swief, T. S. Abdel-Salam, A Reconfigured Whale Optimization Technique (RWOT) for Renewable Electrical Energy Optimal Scheduling Impact on Sustainable Development Applied to Damietta Seaport, Egypt, Energies 11 (3) (2018) .  doi:10.3390/en11030535.
  * [42] J. P. González, A. M. S. Roque, E. A. Pérez, Forecasting functional time series with a new hilbertian armax model: Application to electricity price forecasting, IEEE Transactions on Power Systems 33 (1) (2018) 545–556.  doi:10.1109/TPWRS.2017.2700287.
  * [43] B. H. Zaidi, S. H. Hong, Combinatorial double auctions for multiple microgrid trading, Electrical Engineering 100 (2) (2018) 1069–1083.  doi:10.1007/s00202-017-0570-y.
  * [44] F. Gotzens, H. Heinrichs, J.-F. Hake, H.-J. Allelein, The influence of continued reductions in renewable energy cost on the European electricity system, Energy Strategy Reviews 21 (2018) 71–81.  doi:10.1016/j.esr.2018.04.007.
  * [45] W.-P. Schill, A. Zerrahn, F. Kunz, Prosumage of Solar Electricity. Pros, Cons, and the System Perspective, Economics of Energy & Environmental Policy 6 (1) (2017) 7–31.  doi:10.5547/2160-5890.6.1.wsch.
  * [46] A. Zerrahn, W.-P. Schill, C. Kemfert, On the economics of electrical storage for variable renewable energy sources, European Economic Review 108 (2018) 259–279.  doi:10.1016/j.euroecorev.2018.07.004.
  * [47] J. Olauson, ERA5: The new champion of wind power modelling?, Renewable Energy 126 (2018) 322–331.  doi:10.1016/j.renene.2018.03.056.
  * [48] T. Brown, D. Schlachtberger, A. Kies, S. Schramm, M. Greiner, Synergies of sector coupling and transmission reinforcement in a cost-optimised, highly renewable european energy system, Energy 160 (2018) 720–739.  doi:10.1016/j.energy.2018.06.222.
  * [49] C. Gambardella, M. Pahle, Time-varying electricity pricing and consumer heterogeneity: Welfare and distributional effects with variable renewable supply, Energy Economics 76 (2018) 257–273.  doi:10.1016/j.eneco.2018.08.020.
  * [50] J. Portela, A. Munoz, E. Alonso, Forecasting functional time series with a new hilbertian armax model: Application to electricity price forecasting, IEEE Transactions on Power Systems (2017) 1doi:10.1109/TPWRS.2017.2700287.
  * [51] S. Masum, Y. Liu, J. Chiverton, Multi-step time series forecasting of electric load using machine learning models, in: L. Rutkowski, R. Scherer, M. Korytkowski, W. Pedrycz, R. Tadeusiewicz, J. M. Zurada (Eds.), Artificial Intelligence and Soft Computing, Vol. 10841 of Lecture Notes in Computer Science, Springer International Publishing, Cham, 2018, pp. 148–159.  doi:10.1007/978-3-319-91253-0_15.
  * [52] U. P. Müller, I. Cussmann, C. Wingenbach, J. Wendiggensen, AC Power Flow Simulations within an Open Data Model of a High Voltage Grid, in: V. Wohlgemuth, F. Fuchs-Kittowski, J. Wittmann (Eds.), Advances and New Trends in Environmental Informatics, Springer International Publishing, Cham, 2017, pp. 181–193.
  * [53] M. Kendziorski, M. Setje-Eilers, F. Kunz, Generation expansion planning under uncertainty: An application of stochastic methods to the German electricity system, in: 2017 14th International Conference on the European Energy Market (EEM), 2017, pp. 1–7.  doi:10.1109/EEM.2017.7981891.
  * [54] F. Fusco, S. Tirupathi, R. Gormally, Power systems data fusion based on belief propagation, in: 2017 7th IEEE International Conference on Innovative Smart Grid Technologies (ISGT), 2017.
URL https://arxiv.org/pdf/1705.08815.pdf

  * [55] P. Tafarte, P. Buck, Integration of wind power - 2014; challenges and options for market integration and its impact on future cross-sectorial use, in: 2017 14th International Conference on the European Energy Market (EEM), 2017, pp. 1–5.  doi:10.1109/EEM.2017.7981941.
  * [56] E. H. P. Lee, Z. Lukszo, P. Herder, Aggregated fuel cell vehicles in electricity markets with high wind penetration, in: ICNSC 2018, IEEE, Piscataway, New Jersey, 2018, pp. 1–6.  doi:10.1109/ICNSC.2018.8361362.
  * [57] I. Riepin, T. Mobius, F. Musgens, Integrated electricity and gas market modeling - effects of gas demand uncertainty, in: 2018 15th International Conference on the European Energy Market (EEM), IEEE, 2018, pp. 1–5.  doi:10.1109/EEM.2018.8469790.
  * [58] L. Nacken, T. Möbius, The effects of harmonized European climate policy targets in comparison to national targets utilizing a European electricity market model, in: 2017 14th International Conference on the European Energy Market (EEM), 2017, pp. 1–5.  doi:10.1109/EEM.2017.7981987.
  * [59] M. Robinius, J. Linßen, T. Grube, M. Reuß, P. Stenzel, K. Syranidis, P. Kuckertz, D. Stolten, Comparative Analysis of Infrastructures: Hydrogen Fueling and Electric Charging of Vehicles, Vol. 408 of Schriften des Forschungszentrums Jülich Reihe Energie $\&$ Umwelt / Energy $\&$ Environment, Forschungszentrum Jülich GmbH Zentralbibliothek, Jülich, 2018.
URL http://juser.fz-juelich.de/record/842477

  * [60] E. N. Osegi, Using the hierarchical temporal memory spatial pooler for short-term forecasting of electrical load time series, Applied Computing and Informaticsdoi:10.1016/j.aci.2018.09.002.
  * [61] E. Sharma, Energy forecasting based on predictive data mining techniques in smart energy grids, Energy Informatics 1 (S1) (2018) 982.  doi:10.1186/s42162-018-0048-9.
  * [62] J. Amme, G. Pleßmann, J. Bühler, L. Hülk, E. Kötter, P. Schwaegerl, The ego grid model: An open-source and open-data based synthetic medium-voltage grid model for distribution power supply systems, Journal of Physics: Conference Series 977 (1) (2018) 012007.  doi:10.1088/1742-6596/977/1/012007.
  * [63] U. P. Müller, L. Wienholt, D. Kleinhans, I. Cussmann, W.-D. Bunke, G. Pleßmann, J. Wendiggensen, The ego grid model: An open source approach towards a model of german high and extra-high voltage power grids, Journal of Physics: Conference Series 977 (1) (2018) 012003.  doi:10.1088/1742-6596/977/1/012003.
  * [64] Y. Yaslan, B. Bican, Empirical mode decomposition based denoising method with support vector regression for time series prediction: A case study for electricity load forecasting, Measurement 103 (2017) 52–61.  doi:10.1016/j.measurement.2017.02.007.