# Threshold-Based Algorithms for an Online Rolling Horizon Framework Under
Uncertainty - With an Application to Energy Management

Jens Hönen  Faculty of EEMCS, University of Twente, Enschede, The Netherlands
Johann L. Hurink  Faculty of EEMCS, University of Twente, Enschede, The
Netherlands  Bert Zwart  Department of Mathematics and Computer Science,
Eindhoven University of Technology, Eindhoven, The Netherlands  Centrum
Wiskunde & Informatica (CWI), Amsterdam, The Netherlands

###### Abstract

Decision problems encountered in practice often possess a highly dynamic and
uncertain nature. In particular fast changing forecasts for parameters (e.g.,
photovoltaic generation forecasts in the context of energy management) pose
large challenges for the classical rolling horizon framework. Within this
work, we propose an online scheduling algorithm for a rolling horizon
framework, which directly uses short-term forecasts and observations of the
uncertainty. The online scheduling algorithm is based on insights and results
from combinatorial online optimization problems and makes use of key
properties of robust optimization. Applied within a robust energy management
approach, we show that the online scheduling algorithm is able to reduce the
total electricity costs within a local microgrid by more than 85% compared to
a classical rolling horizon framework and by more than 50% compared to a
tailor-made dynamic, yet still offline rolling horizon framework. A detailed
analysis provides insights into the working of the online scheduling algorithm
under different underlying forecast error distributions.

##  1 Introduction

Solving real-world optimization problems usually involves a large variety of
constraints, representing different aspects of the considered setting, such as
legal regulations, device properties, or physical laws. In addition to the
often highly complex and influencing constraints, large parts of the model
parameters are subject to uncertainty and are therefore not known perfectly in
advance. This uncertainty aspect requires particular solutions techniques,
such as e.g., robust optimization, stochastic programming, or the integration
into a rolling horizon framework. Due to improved forecasts over time or new
measurements, this uncertainty however may reduce over time, leading to
dynamic optimization problems under uncertainty. Such problems appear in many
areas, from energy management, [20], over production planning and scheduling,
[19], to logistics, [39]. What most of these problems have in common is that
decisions need to be made over time. As such, a decision taken now may further
restrict what can be done in future decision steps. Therefore, the impact of
decisions should not only be considered for the given solution known at the
current time (slot) but also some form of look-ahead into the future needs to
be considered. To summarize, the past, the present and the future all impact
the decision-making process, resulting in a highly dynamic optimization
problem under uncertainty.

Within this work, we consider a dynamic optimization problem from the energy
domain as the primary example. It concerns a (joint) energy management
approach for a microgrid. Here, the microgrid is a set of households connected
via the electricity grid (e.g., a neighborhood), which has to make a variety
of time-critical decisions, such as charging and discharging batteries or
electric vehicles (EVs) or placing bids on markets. These decisions have to be
made in a setting with a high degree of uncertainty.

Within the last years, quite some progress has been made within the area of
energy management or energy trading approaches (see e.g., [24], [43] [15],
[18], [59] for recent survey papers and literature studies). Throughout this
research, different techniques, ranging from rolling or receding horizon to
adaptive robust optimization or stochastic programming have been successfully
applied to tackle such (large-scale) dynamic energy management problems under
uncertainty. The advantage of the rolling horizon approaches (see e.g., [31],
[50], [42], [14], [13], [47], [41]) lies within the repeating solving of
subproblems of the original problem. In each solving process, which we denote
as an iteration of the rolling horizon, updated forecasts and new information
of uncertain data may be used to improve the resulting solution. Mathematical
techniques, such as robust optimization or stochastic programming on the other
hand directly focus on the feasibility of the resulting solution by using
additional information of the uncertain data, such as underlying probability
distributions or uncertainty sets. These techniques have become quite popular
for applications within the energy domain (see e.g., [4], [37], [45], [8],
[3], [26], [61], [57]) as they match well with the feasibility focus of the
current energy system. One way how to combine the advantages of robust
optimization and the rolling horizon is to use robust or stochastic techniques
as solution techniques for the iterations of a rolling horizon (see e.g., [6],
[55], [46], [30], [10], [40], [35], [28], [33], [34], [21], [11]). This allows
to use updated (real-time) information on uncertain data to incorporate the
uncertainty and reduce stochasticity.

One possible disadvantage of the classical rolling horizon framework is the
use of equidistant spacing between iterations, which often does not fit well
with the uncertain nature of parameters. Photovoltaic (PV) generation, for
example, is assumed to be of major importance for the energy transition (see
e.g., [29]), but also difficult to forecast. As such, it is an uncertain
parameter within an energy management problem, but obviously, its uncertainty
is not spread equally among the day but is limited to daytime. Therefore, the
iterations of a classical rolling horizon framework, which are scheduled
during the night, do not contribute to an improvement of the solution as no
new short-term PV forecasts are available. To be able to better capture the
improvements in PV forecasts, in earlier work [25] we proposed a dynamic
rolling horizon framework. The key idea of this dynamic rolling horizon
framework is to go beyond the fixed time distance between consecutive
iterations and schedule them in a more flexible way to better capture the
updated PV forecasts. For this, we developed a dynamic (offline) scheduling
tool, which identifies good starting time slots for the iterations of a
rolling horizon. This scheduling tool is based on a version of a knapsack
problem and it uses the structural knowledge of the underlying uncertainty
sets from robust optimization.

Although the combination of the dynamic scheduling tool with a rolling horizon
yields large improvements over the classical rolling horizon, some weaknesses
have been identified. Firstly, the knapsack problem determines starting time
slots based on average realizations of future uncertainty. This may be a
reasonable choice if the expectation of the uncertainty realization is close
to the average. However, for a skewed underlying uncertainty distribution,
this could considerably affect the outcome of the optimized starting time
slots. The second disadvantage follows from the offline nature of the
decision-making process and is even more important. The decision when to start
the iterations of the rolling horizon is already made at the start of the
considered time horizon, and therefore there is no option to react to
particularly good (or bad) forecasts or observations of uncertainty.
Specifically, given the nature of the considered problem, it is of high
importance to be able to react to extreme or unusual events.

Based on the above considerations, within this work, we design an online
version of the dynamic rolling horizon framework, which improves upon both of
the above-mentioned disadvantages. Instead of deciding upon the starting time
slots in advance, the online rolling horizon framework decides on the fly
whether to start an iteration or not. Thereby, it is able to react to updated
forecasts or observed realizations of uncertainty and can make better
decisions regarding the starting of iterations. In a first step, we generalize
the knapsack formulation, first introduced in [25], beyond the explicit
application of an energy management problem. We then reduce the generalized
formulation to an instant of the $k$-edge longest path problem in directed
acyclic graphs, which we show can be solved efficiently via a dynamic
programming approach. The outcome of this path problem just provides the
threshold for the online threshold algorithm, which is run for each time slot
to decide whether or not to start an iteration of the rolling horizon. The
online threshold algorithm is inspired by algorithms with a constant
competitive ratio for various online problems, such as the online knapsack,
multi-secretary, or prophet inequality problem. In addition, it makes use of
the main principles of robust optimization and is thereby able to react to
extremely good or bad forecasts or realizations of uncertainty. Within a case
study, we show that the online rolling horizon framework is able to improve
the solution by over 85% compared to the classical rolling horizon approach
with a fixed step size, and by over 50% compared to a tailor-made offline
rolling horizon scheme, as presented in [25]. To sum up, the main
contributions of this work are:

  * •

We propose a novel online rolling horizon framework, which can adapt the
starting time slots of its iterations to updated forecasts and observed
uncertainty.

  * •

We derive an efficient algorithm for solving the $k$-edge longest path problem
subject to the constraint that a given subset of the nodes has to be part of
the path.

  * •

We conduct a detailed case study, which shows the potential of the online
rolling horizon framework compared to various offline rolling horizon schemes.

This work is an extension of earlier work on dynamic scheduling of starting
time slots of a rolling horizon in the context of a local energy management
problem under uncertainty, [25]. The considered underlying setting is
therefore the same, but both, the used techniques to design the online
framework, as well as the analysis, have not been considered before. In
addition, a refined analysis of the knapsack problems as well as the
underlying error distributions is presented.

The paper is structured as follows: The central mathematical optimization
model is derived and presented in Section 2, while Section 3 introduces the
different online scheduling algorithms for the rolling horizon framework.
Section 4 presents the application scenario of a robust energy management
approach and in Section 5, we present, analyze and discuss the results of a
case study. We conclude the work in Section 6 and provide interesting research
directions for future work.

##  2 Model

In this section, we introduce the essential mathematical components of the
online algorithms, presented in Section 3. Inspired by the results of the
knapsack approach in [25] to identify good starting time slots for the
iterations of a rolling horizon, we first generalize the knapsack model beyond
the specific application of a robust energy management approach. In a second
step, we reduce the generalized knapsack problem into a longest path problem
and provide insights into the computational complexity and running time.

###  2.1 Input Parameter and Notation

To decide when to execute iterations of the rolling horizon, we consider the
following input data:

  * •

In applications of a rolling horizon framework, the considered time horizon of
the problem is usually split up into a set of equidistant time slots.
$\mathcal{T}=\left\\{0,1,\ldots,T\right\\}$ denotes the set of time slots. As
we consider an ongoing rolling horizon, we assume that an initial solution is
given, which could be the solution of the last iteration of the previous time
horizon. Within $\mathcal{T}$, let time slot $0$ represent the time slot of
this initial solution.

  * •

$c\in\mathbb{R}_{\geq 0}^{|\mathcal{T}|\times|\mathcal{T}|}$ represents the
information gain over time within the rolling horizon, whereby the parameter
$c_{s,t}$ denotes the information gained when starting an iteration of the
rolling horizon at time slot $t$, given that the previous iteration started at
time slot $s$.

  * •

$k\in\mathbb{N}_{>0}$ is a positive integer denoting the maximal number of
iterations of the rolling horizon over the time horizon $\mathcal{T}$. This
upper bound on the number of iterations may be imposed by various aspects,
such as e.g., computational resources, limited (desired) communication, or
other setting-dependent constraints.

  * •

$\mathcal{M}=\left\\{i_{0},i_{1},\ldots,i_{m}\right\\}\subset\mathcal{T}$ is a
given set of time slots, which needs to be part of the selected time slots,
where an iteration of the rolling horizon is executed. As time slot $0$
corresponds to the initial solution, we assume that $0=i_{0}\in\mathcal{M}$.
In general, $\mathcal{M}$ could represent certain time slots, in which
decisions need to be communicated or submitted to markets or other internal or
external entities within the considered setting.

Within the following, we introduce two different models, which are essential
components of the online scheduling algorithms presented in Section 3. As
these models are based on well-known combinatorial optimization problems, we
stick to their usual notation. Figure 1 provides a mapping between the
notation of the various models and the online scheduling algorithm.

Figure 1: Overview and mapping between the used notation within the different
models.

###  2.2 Knapsack Formulation

As for the knapsack model in [25], the items of the knapsack correspond to the
potential starting time slots of iterations of the rolling horizon, while the
valuation of an item corresponds to the additional information it can provide
when starting an iteration in this time slot. In our setting, all items have a
weight of one, while the knapsack size corresponds to the maximal number of
iterations during the time horizon. This also implies that we have a
topological ordering on the items of the knapsack problem, which directly
follows from the structure of the time slots.

Let $x_{t}$, $t\in\mathcal{T}$, be a binary variable indicating whether to
include item $t$ into the knapsack or not. As the valuation of an item $t$
depends on the choice of its predecessor $s$, let $y_{s,t}$, $s<t$, be an
auxiliary binary variable to link the chosen items to their corresponding
valuation. The objective is to maximize the value of the chosen items:

$\max\sum_{s,t\in\mathcal{T}}c_{s,t}y_{s,t}.$ (1)

The classical knapsack constraint, which limits the number of items to at most
$k$, is

$\sum_{t\in\mathcal{T}}x_{t}\leq k+1.$ (2)

Note that we use an upper limit of $k+1$, as item $0$ is also included, but
should not count as an online iteration. To ensure that the items in
$\mathcal{M}$ are chosen, we add constraints

$x_{t}=1\quad\forall t\in\mathcal{M}.$ (3)

The following constraints link the variables $x_{t}$ with the auxiliary
variables $y_{s,t}$ and thereby establish a connection to the valuations:

$y_{s,t}\leq x_{t}\quad\forall s,t\in\mathcal{T},$ (4) $y_{s,t}\leq
x_{s}\quad\forall s,t\in\mathcal{T}.$ (5)

To ensure that only the valuations between neighboring items are counted, we
ensure that each item counts at most once as the beginning and at most once as
the finishing item within the $y_{s,t}$ variables, which have a value of 1:

$\sum_{s\in\mathcal{T}}y_{s,t}\leq 1\quad\forall t\in\mathcal{T},$ (6)
$\sum_{t\in\mathcal{T}}y_{s,t}\leq 1\quad\forall t\in\mathcal{T}.$ (7)

To ensure that only the valuations between neighboring items are counted, we
add the following constraints:

$1-x_{t}+y_{s,t}\geq y_{s,l}\quad\forall s,t,l\in\mathcal{T},s<t<l.$ (8)

If items $s<t<l$ are all taken, then $x_{t}=1$. The above constraints then
simplify to $y_{s,t}\geq y_{s,l}$, which together with constraint (7) ensures
that $y_{s,l}=0$ and the valuation $c_{s,l}$ does not add to the objective. If
$s$ is not taken, then all variables $y_{s,.}$ are automatically zero and if
$t$ is not taken ($x_{t}=y_{s,t}=0$), then the constraint simplifies to $1\geq
y_{s,l}$, which does not lead to any restrictions. Hence, the objective
function (1), together with constraints (2)-(8) forms the knapsack problem.

###  2.3 Reduction to Graph-Based Problem

Analyzing constraints (6)-(8), it becomes obvious that the $y$ variables
actually have to form a path on some graph over $\mathcal{T}$. Constraints (6)
and (7) ensure that there is at most one in-going and at most one out-going
arc for each pair $s,t\in\mathcal{T}$, while equation (8) ensures that only
arcs between consecutive time slots may be taken. Coupled with the objective
(1) and the non-negativity of the $c$ values, an optimal solution corresponds
to a path of at most $k$ arcs. Summarizing, the above knapsack problem can be
reduced to a longest path problem with at most $k$ arcs, visiting all nodes in
$\mathcal{M}$, on a directed graph, spanned on the set of time slots
$\mathcal{T}$.

To formalize, the graph is a complete directed acyclic graph (DAG)
$\mathcal{G}=(\mathcal{V},\mathcal{A},c)$, in which the node set $\mathcal{V}$
corresponds to the time horizon $\mathcal{T}$, enlarged by an artificial node
$T+1$. The set of directed arcs $\mathcal{A}$ consists of arcs $(s,t)$ for all
pairs $s,t\in\mathcal{V}$, $s<t$, and the arc length $c$ is given by the
information gains $c$. Furthermore, the natural ordering of the time slots
corresponds to the unique topological ordering of the nodes of the graph. For
completeness, the arc length for the arcs going into the artificial node $T+1$
is given by $c_{s,T+1}=0$. The knapsack problem of finding an optimal solution
with at most $k$ items, using all items in $\mathcal{M}$ now translates into
the problem of finding a $0-(T+1)$-path of at most $k+1$ arcs, which visits
all nodes in $\mathcal{M}$ and maximizes the length along this path.

Due to the topological ordering of the DAG $\mathcal{G}$, this problem can be
solved using two different dynamic programming approaches in
$\mathcal{O}(T^{2}k)$ time. In a first step, we compute for $j=0,\ldots,m$ the
longest paths between nodes $i_{j},i_{j+1}\in\mathcal{M}$ with exactly
$h\in\\{1,\ldots,\min(k+1,i_{j+1}-i_{j})\\}$ arcs, where $i_{m+1}=T+1$. This
can be done in time $\mathcal{O}(T_{i}^{2}k)$ for each pair $i_{j}$ and
$i_{j+1}$, whereby $T_{i}=i_{j+1}-i_{j}$. Summing up over all pair of nodes
$i_{j},i_{j+1}$, we have a total complexity of
$\sum\mathcal{O}(T_{i}^{2}k)\leq\mathcal{O}(T^{2}k)$, as $\sum T_{i}=T$. In a
second step, we reduce the original graph to the node set
$\mathcal{M}\cup\left\\{T+1\right\\}$ and use the previously computed longest
paths with $h$ arcs between neighboring nodes. By a second dynamic programming
approach, the longest path from node $0$ to node $T+1$ using at most $k+1$
arcs can be calculated in a straightforward way in an iterative fashion. The
running time of this second dynamic program is $\mathcal{O}(mk^{2})$, leading
to an overall complexity of $\mathcal{O}(T^{2}k)$, as $T>k>m$.

##  3 Online Algorithm

In this section, we first review the literature on similar online optimization
problems and then introduce and derive the main principles and algorithms for
the online scheduling of the rolling horizon.

###  3.1 Online Literature

As mentioned in Section 1, an online approach to schedule the starting time
slots of a rolling horizon may have several benefits over an offline
scheduling approach. To gain insights into the working of online algorithms, a
review of solution approaches for various online combinatorial optimization
problems is given, which are based on a similar online problem structure as
the online scheduling of the iterations of a rolling horizon in this study.
Note that the reviewed literature analyzes the online problems from a
theoretical perspective, where the main goals are to derive (constant)
competitive online algorithms. Although this theoretical focus differs from
the rather practical application in our study, high-level concepts and ideas
can still be applied to our problem.

Online optimization has been an important research direction in the area of
(combinatorial) optimization for many years now. Online problems, in which
items arrive one by one, and for each item it has to be decided irrevocably
whether to keep or discard it, can be found in online versions of the knapsack
problem, the (multi-)secretary problem, [12], resource assignment problems,
[9], or prophet inequality problems, [44]. Next to some negative results on
the competitiveness of online algorithms for some of these problems [36],
promising online algorithms have been developed under some (mild) assumptions.
These assumptions range from knowledge of distributions or ranges of values
for certain item parameters ([36], [58], [49]), to the order in which items
may arrive ([1], [32]). Independent of these different assumptions, many of
the proposed competitive online algorithms are based on the same high-level
solution approach with small differences in specific elements of the
algorithms, often reflecting the various assumptions.

In [1], the values of the items are drawn independently from known
distributions and the items arrive in a uniformly random order. The focus is
to derive a static threshold, such that the values of the first $k$ items with
values exceeding this threshold are maximized in expectation. The decision
rule is therefore based on two important parameters, namely the value of the
items, as well as the static threshold.

In [54], the used threshold is not static, but a linearly increasing function
of the utilization rate of the knapsack (in multiple dimensions). In addition,
the weight of the item is also included in the threshold. Again, the value of
an item gets known as soon as the item arrives and an irrevocable decision
regarding the usage of this item has to be made. Furthermore, a second online
algorithm is proposed, which admits an exponential threshold function. This
threshold function is again increasing in the utilization rate of the knapsack
and also includes the weight as a factor. In comparison to the linear
threshold function, this exponential threshold is more conservative in
admitting items and prefers to reserve available space for future high-value
items. Further exponential threshold functions depending on the utilization of
the knapsack are presented in [58], [49], [56], and [48] among others. In
addition to the utilization rate of the knapsack, in [58], [56] upper and in
[58], [56], [48] lower limits on the value to weight ratio of the items, or
upper limits on the item size, [49], are assumed to be known.

Instead of using the knapsack utilization rates as the base for the
thresholds, another approach for a threshold is to first observe some of the
arrivals and then use the observed data to derive a threshold (see e.g. [49],
[32], [27], [2], [5], [22]). This threshold is based on the values of the
already observed items, similar to solution approaches for the classical
secretary problem, in which the algorithm first observes a certain fraction of
the online input, and the largest observed value is then used as the threshold
for the remaining online input (see [12]). In [32] and [27], the set of
values, which should first be observed are referred to as the history set H,
and considered to be part of the input and not of the actual online problem,
in which decisions are made. In case $H$ is small, the first items in the
online phase are still only observed to gain additional information, similar
to [12]. In [22], various threshold-based online algorithms are proposed. Some
directly rely on the original algorithm for the classical secretary problem,
[12], while others randomly select the number of items to first observe. In
[2] on the other hand, the set of items is split up into $L$ subsets, and
after each round, the threshold is updated based on the solutions of the
previous subset of items. A similar approach is used in [5], in which some of
the items arrive randomly within the time horizon $[0,1]$, and the split into
subsets is done on the time horizon with updated thresholds for each interval.

A class of online problems, which closely resembles the considered online
scheduling problem of a rolling horizon framework, are prophet inequality
problems. In particular combinatorial prophet inequality problems, first
introduced in [44] and improved in [7], are built upon a very similar
structure. In these problems, the decision maker is faced with a sequence of
$n$ items, drawn from $n$ known (discrete) distributions. At each iteration,
an item is drawn from the corresponding distribution and presented to the
decision maker, who must decide irrevocably whether to take the item or not,
subject to matroid constraints. The goal is to maximize a submodular function
$f$ over the set of chosen items. There are two main differences to the
considered online scheduling problem of a rolling horizon. The first is the
discrete nature of the underlying distributions. This difference may be
overcome by approximating the continuous probability distributions by means of
discrete distributions without losing too much information. The second
difference lies within the knowledge of future distributions of the
combinatorial prophet inequality problem. In our setting, we do not know the
probability distributions, and therefore we are not able to directly apply the
proposed algorithms to our case. In contrast to the previously considered
literature, the algorithm is not based on an online threshold algorithm but is
heavily dependent on Online Contention Resolution Schemes, which is a rounding
technique for online optimization problems, [17].

###  3.2 Online Threshold Algorithms

Summarizing the above-presented literature, the key similarity of most of the
reviewed literature is the structure of how to decide whether to take item $t$
or not. This structure can be generalized and compressed to the following
rather simple equation:

$c_{t}\geq f(t,x)\tau,$ (9)

where $c_{t}$ is the value or contribution of item $t$, $f(t,x)$ is a factor,
which may depend on time slot $t$ and further information $x$, such as how
many items have already been taken or proposed, and $\tau$ is a threshold.
Note that compared to the considered literature, the threshold is split into a
threshold and a factor. If the value of the item exceeds the (factored)
threshold, then the item is taken. Translating this simple decision process
into the setting of an online scheduling problem for a rolling horizon, $\tau$
still may remain a threshold to be determined, while $f(t,x)$ may represent
the possible dynamic nature of the threshold. On the other hand, the value
$c_{t}$ of the current time slot $t$ may translate to the additional
information, which the algorithm has access to in time slot $t$ compared to
the last starting time slot. In contrast to the reviewed online literature, in
our case, we are not simply given such a value $c_{t}$ but have to compute it.

Based on the principle of equation (9) as well as the insights from the online
literature, we identify three main lines of online algorithms, each with a
distinct difference in either the value of a time slot or the threshold:

  * •

Average-Realizations (AR) Approach: Based on the longest path model introduced
in Section 2 to determine optimal starting time slots, we define the
individual contributions of each of the proposed optimal starting time slots.
We use average realizations or predictions of the uncertainty as parameters
for the path problem. After computing the individual contributions, we apply
some function $g$ on the vector of contributions and use the corresponding
result as the threshold. The contribution of the current time slot $t$ is
computed based on the same type of data, but instead of using average
realizations and forecasts, we can now use the actually observed realizations
and current forecasts.

  * •

Historical-Realizations (HR) Approach: Instead of using the longest path model
with average realizations as the values, we may also use historical data to
find optimal starting time slots for past days in hindsight. This historical
data can be seen as samples from the underlying, unknown probability
distribution, as used in prophet inequality problems, or as the set of items
that should first be observed, as done in several online knapsack or secretary
problems. Based on the chosen starting time slots, the individual
contributions can easily be computed and used as the threshold. The
contribution of time slot $t$ is again computed based on actual observations
and updated forecasts.

  * •

Partial-Realizations (PR) Approach: Instead of using the longest path model
only once to compute individual contributions of optimal starting time slots,
the model can also be used in an iterative online fashion. For each time slot,
the model is run with updated real-time data, such as current forecasts and
observed realizations of the previous time slots $s<t$. After solving the path
problem with updated information, the decision of whether to start an
iteration during the current time slot $t$ depends on the current solution. If
node $t$ is part of this path, an iteration of the rolling horizon is started,
else we repeat the process for the next time slot $t+1$.

In the following subsections, we focus on how to determine the contribution,
threshold, and factor for time slot $t$ for each of the three main lines,
given that the last starting time slot of the rolling horizon was a time slot
$t_{l}<t$.

####  3.2.1 Contribution

In contrast to the simply observable value of an arriving item within an
online knapsack, secretary, or prophet inequality problem, in our case, the
value for the time slots needs to be computed. Hence, in the following, we
refer to this value as the contribution of the current time slot.

  * •

For the AR approach, we need to compute the contribution based on the
differences in available information between the current time slot $t$ and the
last starting time slot $t_{l}$. Depending on the application, the available
information can either be in the form of updated forecasts or observed
realizations of uncertainty since the last start.

  * •

The contribution for the HR approach is the same as for the AR approach.

  * •

The PR approach uses the optimal solution of the path model with updated
values to derive the contribution. If the current time slot $t$ is part of the
optimal path, we define the contribution as one, and if it is not, we simply
set the contribution to zero.

####  3.2.2 Threshold

All three main approaches (AR, HR, PR) derive their thresholds based on
different data sets. While the AR approach is based on average values, the HR
approach uses historical data to compute its threshold. The PR approach
already uses its data within the computation of the contribution and can
therefore make use of a very simple threshold. Within the following discussion
of these thresholds, some (high-level) ideas from the reviewed literature can
be identified.

  * •

The threshold for the AR approach is based on the optimal solution of the path
model with average values as input parameters. Instead of directly using the
nodes within the optimal path as fixed starting time slots of the iterations
of the rolling horizon, as done in [25], the AR approach instead uses the
optimal objective value to compute its threshold. The objective value can be
split up into individual contributions of the nodes within the optimal path.
As the vector of individual contributions cannot directly be used as the
online threshold, which consists of a single value, we need to apply some
function on the vector to project it to a single number. Instead of using
either the maximal, minimal, or average observation as the threshold, we test
and analyze the impact of different percentiles as the threshold.

  * •

The threshold for the HR approach is also based on the individual
contributions of the nodes of the optimal path of the path model. Instead of
using average data for the values as done for the AR approach, the HR approach
is based on historical data. We assume to have access to $N_{HR}$ such
historical data sets, which represent ’similar’ conditions as predicted for
the current time horizon. This historical data is then used to compute optimal
solutions in hindsight. The individual contributions of each of the $N_{HR}$
optimal paths are then grouped together and the percentile function is applied
to generate one single value based on the vector of individual contributions.

  * •

The threshold for the PR approach is relatively simple compared to the
previous two approaches. As the contribution is either 0 or 1, represented by
the optimal path, we simply set the threshold to 1.

####  3.2.3 Factor

Based on the literature review of comparable online combinatorial optimization
problems, most approaches use some form of dynamically changing threshold,
often based on the utilization rate. The thresholds introduced in Section
3.2.2 do not reflect this dynamic nature yet. Therefore, we have introduced
the factor $f(t,x)$ in equation (9) to account for that. In addition, insights
into the structure of the underlying uncertainty as well as the shape of the
contributions may be used to design ’tailor-made’ factor functions $f(t,x)$.
These factors $f(t,x)$ can be applied to the thresholds of the AR and HR
approaches. Based on insights gained during the testing, the values of the
factor functions should be centered around 1 to not change the threshold too
much. To keep the functions general, we introduce a lower bound $L$ and an
upper bound $U$ for the functions, whereby we assume $L<1<U$. The considered
parameterized factor functions are then:

  1. 1.

Constant: A constant factor $f(t,x)=1$, leaving the ’pure’ threshold, similar
to ideas in secretary or prophet inequality problems (see e.g., [1], [12]).

  2. 2.

Step-wise constant: To discourage long periods without starting any iteration,
we introduce a step-wise constant factor. This factor starts with a constant
factor of 1 but decreases to a value of $L$ in case the time since the last
starting time slot $t_{l}$ exceeds a certain setting-specific threshold $R$.
This decrease should encourage to start another iteration, as the factored
threshold also decreases, making it easier to start another iteration.
Concrete, we use

$f(t,x)=\begin{cases}1&\text{if }t-t_{l}\leq R\\\ L&\text{if
}t-t_{l}>R\end{cases}.$ (10)

  3. 3.

Linearly increasing: Inspired by the linear threshold function presented in
[54], the following factor is considered:

$f(t,x)=(U-L)x+L.$ (11)

Note that this factor is not based on the time slot $t$, but rather on the
iteration usage rate $x$, which represents the percentage of already used
iterations during the time horizon. The main idea behind an increasing factor
depending on the number of already started iterations is that in the
beginning, it should be easier to start an iteration, but the more iterations
have already started, the more difficult it should get and the ’pickier’ the
algorithm should be.

  4. 4.

Exponentially increasing: Much of the reviewed literature is based on an
exponential threshold of some form, see [58], [49] among others. They are
based on the utilization rate, a concept that we also use within this factor
function. In contrast to exponential thresholds, which admit any item up to a
given utilization rate (see e.g., [58]) we slightly lower the threshold in the
beginning and then directly increase it. This leads to the following factor
function

$f(x)=a\exp(cx)+b,$ (12)

where $a,b$ and $c$ are chosen such that $f(0)=L$ and $f(1)=U$. In Figure 2,
$c$ is chosen to be 2.5, while $L=0.8$ and $U=1.2$.

  5. 5.

Quadratically increasing and decreasing: The idea of starting with a lower
threshold and then making it more difficult to start new iterations, as done
for the linear and the exponential factors, has been inspired by the reviewed
theoretical work on online-competitive algorithms. In practice, on the other
hand, this increasing factor leads to situations, in which not all of the
possible iterations are used, which leaves potential unused. To counter this,
we let the quadratic factor not continue to increase with the utilization rate
$x$, but decrease it again for $x>0.5$. We define the function as follows:

$f(x)=a(x-0.5)^{2}+b,$ (13)

where $a$ and $b$ are again chosen such that $f(0)=f(1)=L$ and $f(0.5)=U$.

  6. 6.

Factored threshold based on [58]: Next to concepts from literature, we may
also directly use a (slightly modified) version of the threshold function
presented in [58]. However, as the assumption of a strictly positive upper and
lower limit on the value does not hold in this study, we simply use the
minimal and maximal contribution values of the HR knapsack problem as the
lower and upper limit.

$0$$0.2$$0.4$$0.6$$0.8$$1$$0.8$$1$$1.2$iteration usage rate $x$factor
valueconstantlinearexponentialquadraticexponential [58] Figure 2: Plot of the
different factors, given a lower bound of $L=0.8$ and an upper bound of
$U=1.2$

##  4 Application to an Energy Management Problem Under Uncertainty

Within this section, we use an energy management problem under uncertainty for
a microgrid as an example of applying the introduced online algorithms for the
scheduling of a rolling horizon. We shortly introduce the energy planning
problem, including the involved participants and components, and then focus on
the parameters needed as input for the models introduced in Section 2. Within
the energy management problem, we apply robust optimization to deal with
uncertainty in the data but treat the robust formulation as a black-box within
this work. As this work is a continuation of earlier work, we refer the
interested reader to [25], Sections 2 and 3, for further details regarding the
setting of the energy management problem. In addition, a comprehensive
explanation of the robust energy management formulation and the classical and
dynamic, yet offline rolling horizon frameworks can be found there. We
conclude the section with a detailed overview of the needed input parameter
for the online algorithms.

###  4.1 Robust Energy Management Problem

####  4.1.1 Setting

The considered dynamic problem is an energy management problem for a microgrid
under uncertainty, in which households may have controllable devices, such as
EVs, batteries, or PV systems. Hereby, the time horizon is discretized and
spans multiple days. Furthermore, two different electricity markets are
available to purchase or sell electricity. We assume that a microgrid operator
(MGO) acts as an aggregator for the microgrid and is therefore responsible for
the buying and selling decisions at the markets.

The two electricity markets are the day-ahead market and the intraday market,
which work as their names indicate. The decisions for the day-ahead market
have to be made and submitted the day before the actual usage. Given the time
distance between submitting the buying and selling decisions and their actual
implementation, deviations from the planned energy usage may occur. The MGO
can use the intraday market to react to these deviations by deciding just
before a time slot $t$ how much to buy or sell at the intraday market
(additionally to the day-ahead market). The buying and selling prices for time
slot $t$ in this market are denoted with $\pi^{ID,buy}_{t}$ and
$\pi^{ID,sell}_{t}$ and with $\pi^{DA}_{t}$ for the day-ahead market.

The considered devices and loads of the household are the following:

  * •

Prosumer load: Each household has an inflexible load profile, which has to be
served. We do not assume that any of this load can be curtailed or shifted to
other time slots.

  * •

PV system: Households may be equipped with a PV system. Let
$\hat{p}^{PV,j}_{t}$ denote the produced electricity of PV system $j$ during
time slot $t$. The MGO can curtail the generation if needed.

  * •

Battery: A battery can be used to shift the demand or production of
electricity through time.

  * •

EV: The EV works in a similar way as the battery in that it can be charged and
discharged. A major difference is the availability of the EV, which is
limited, as well as the EV demand, which reduces its state of charge.

####  4.1.2 Uncertainty

For the above-presented setting of a microgrid energy management problem, we
consider multiple sources of uncertainty. We first reason why parameters are
assumed to be uncertain, and then provide the corresponding notation and
uncertainty sets:

  * •

Prosumer load: The household load of an individual household is heavily
influenced by often spontaneous decisions and actions of its residents. Hence,
it is not possible to perfectly predict individual household loads for even
short-term time horizons.

  * •

PV generation: Although PV forecasting has continued to improve over the last
years, still deviations between the predicted value and the actual generations
do appear. A general trend is that short-term forecasting often yields better
results than long-term forecasting of PV generation [23]. We include this
insight into the modeling of the PV uncertainty in the following way. We first
split up the uncertain parameter $\hat{p}^{PV}_{t}$ into a known and an
uncertain part,

$\hat{p}^{PV}_{t}=p^{PV}_{t}(1+\alpha^{PV}_{t}u^{PV}_{t}),$ (14)

where $p^{PV}_{t}$ corresponds to the predicted value, while
$\alpha^{PV}_{t}u^{PV}_{t}$ represents the uncertain part. This uncertain part
can be further split up into $u^{PV}_{t}$, which is a random variable,
modeling the true realization of the uncertainty, and $\alpha^{PV}_{t}$, which
defines how large the uncertainty can potentially be. Note that
$\alpha^{PV}_{t}$ depends on time slot $t$, which is how the different
accuracies of the forecast are included in the model. In particular during the
rolling horizon framework, $\alpha^{PV}_{t}$ and $p^{PV}_{t}$ for a given
future time slot $t$ can change depending on when the forecast is made. For
using robust optimization, we define the uncertainty set for $u^{PV}_{t}$ as a
budget uncertainty set:

$U^{PV}=\left\\{u\in\mathbb{R}^{|\mathcal{T}|}|\|u\|_{\infty}\leq
1,\|u\|_{1}\leq\Gamma^{PV}\right\\}.$ (15)

In addition, we assume that the PV forecasts are time-dependent, that is they
improve over time, meaning that the uncertainty sets get smaller, the closer
we are to the corresponding time slot. For this, we need to introduce another
index for the PV data to indicate when the forecast has been made. Let
$p^{PV}_{t,s}$ denote the PV generation forecast for time slot $t$, made at
time slot $s$. The same applies to $\alpha^{PV}_{t,s}$, which is predicted at
time slot $s$ for time slot $t$. In case only one time slot index is present,
we assume w.l.o.g. that the initial forecast of the beginning of the time
horizon is used. One important assumption on the resulting sequence of PV
forecasts for a fixed time slot $t$ is that they are contained in each other,
i.e.,

$p^{PV}_{t,s}(1-\alpha^{PV}_{t,s})\geq p^{PV}_{t,l}(1-\alpha^{PV}_{t,l}),$
(16)

and

$p^{PV}_{t,s}(1+\alpha^{PV}_{t,s})\leq p^{PV}_{t,l}(1+\alpha^{PV}_{t,l}),$
(17)

for time slots $l\leq s\leq t$. This ensures that the uncertainty intervals
for a specific time slot $t$ can only improve.

  * •

EV demand: Although the EV demand for a known trip can be estimated quite
well, in practice various unknown factors, such as vehicle heating or cooling,
traffic jams or small detours can affect the actual demand. Hence, we also
consider the EV demand to be uncertain.

  * •

EV arrival and departure times: Even though most people have some level of
routine in their daily working patterns, unforeseen events, such as traffic
jams, or an unplanned detour to the supermarket can always change arrival and
departure times.

  * •

Market prices: As the prices of the electricity markets are based on the
actual demand and supply for a time slot, we assume that the exact prices are
not known in advance.

####  4.1.3 Robust Energy Management Approach

For the introduced setting, the goal of the MGO is to minimize the electricity
costs of the microgrid, while maintaining a feasible schedule at all times.
For this, the MGO needs to decide when and how much electricity to buy and
sell at the two considered electricity markets. In addition, it also needs to
decide on the charging and discharging schedules of batteries and EVs, while
satisfying the regular household demand. All these decisions have to be made
under the assumption that the exact values of demand, generation, and prices
are unknown beforehand.

###  4.2 Application to Online Framework

Determining the values and contributions needed for the online scheduling
framework for this robust energy management problem is mainly based on the
improvements in PV forecast over time. The conservative approach of robust
optimization enforces that the obtained solution is feasible w.r.t. all
possible realizations of the uncertain parameter. In the case of the uncertain
PV generation, this translates into using at most the lower limit of the PV
uncertainty interval. With each iteration, we get access to updated forecasts,
and thereby also to (improved) lower limits of the PV uncertainty intervals.
For the three considered different online scheduling algorithms, we have to
estimate how much this lower limit will improve. This results in the following
values and parameters:

  * •

AR approach: Assuming average contributions, we use historical knowledge on
how the uncertainty sets for a given time slot $t$ shrink over time, as
assumed by equations (16) and (17). Let $\beta^{PV}_{l,t}\in\left[0,1\right]$
be the reduction factor of the PV uncertainty interval for time slot $l$,
expressing an improved forecast at time $t$ compared to the initial (long-
term) forecast at time $0$. Then the average improvement of the lower limit of
the PV uncertainty interval can be expressed as
$p^{PV}_{l}\alpha^{PV}_{l}\beta^{PV}_{l,t}$. Hence, the average improvement
for starting an iteration at time slot $t$ in relation to the last start at
time slot $s$ is given by

$c_{s,t}=\sum_{l=t}^{|\mathcal{T}|}p^{PV}_{l}\alpha^{PV}_{l}\big{(}\beta^{PV}_{l,t}-\beta^{PV}_{l,s}\big{)}.$
(18)

This improvement can then be seen as the additional available PV generation
compared to time slot $s$. These values are used as the directed arc lengths
for the longest path model.

Within the online process of deciding whether to start an iteration at time
slot $t$ or not, we need to compare the threshold, which is (loosely) based on
the above-presented values, with the contributions of time slot $t$, assuming
we would start an iteration. Therefore, we use the current data and forecasts
of time slot $t$ and compute the improvements over the forecasts made at the
last starting time slot $t_{l}$, resulting in

$\tilde{c}_{t}=\sum_{s=t}^{T}(p^{PV}_{t_{l},s}(1-\alpha^{PV}_{t_{l},s})-p^{PV}_{t,s}(1-\alpha^{PV}_{t,s})),$
(19)

as the contribution of the current time slot $t$.

  * •

HR approach: We translate each of the given data samples into a longest path
problem and thereby determine the optimal starting time slots of the
iterations in hindsight. Given that, for each data sample, we know all
historical PV forecasts, we compute the value $c_{s,t}$ for time slots
$s<t\in\mathcal{T}$ by

$c_{s,t}=\sum_{l=t}^{|\mathcal{T}|}\big{(}p^{PV}_{l,t}(1-\alpha^{PV}_{l,t})-p^{PV}_{l,s}(1-\alpha^{PV}_{l,s})\big{)}.$
(20)

For a fixed time slot $l>t$, this can be seen as the improvement in the lower
bound of the uncertainty interval of the PV production given the new starting
time slot $t$ over the previous prediction made at time slot $s$.

Remind that for the HR approach, the same threshold (19) as for the AR
approach is used.

  * •

PR approach: For the current time slot $t$, we combine the data of the average
realizations with observations of the past. Let $t_{l}$ again be the last
realized starting time slot. Then, we have four different cases:

    1. 1.

For arc $(t_{l},t)$, we simply use the predicted forecasts, and subtract the
lower limits of the predicted PV uncertainty intervals:

$c_{t_{l},t}=\sum_{k=t}^{|\mathcal{T}|}\big{(}p^{PV}_{k,t}(1-\alpha^{PV}_{k,t})-p^{PV}_{k,t_{l}}(1-\alpha^{PV}_{k,t_{l}})\big{)}.$
(21)

Due to constraint (16), the length of the arc $(t_{l},t)$ is always positive.

    2. 2.

For arcs $(t_{l},l)$ with $l>t$, we again apply the idea of average reductions
for future forecasts, while for time slot $t_{l}$, we can simply use the lower
limits of the predicted PV uncertainty intervals. Hence, we have

$c_{t_{l},l}=\sum_{k=l}^{|\mathcal{T}|}\big{(}p^{PV}_{k,t}(1-\alpha^{PV}_{k,t}+\alpha^{PV}_{k,t}(\beta^{PV}_{k,l}-\beta^{PV}_{k,t}))-p^{PV}_{k,t_{l}}(1-\alpha^{PV}_{k,t_{l}})\big{)},$
(22)

where the
$p^{PV}_{k,t}(1-\alpha^{PV}_{k,t}+\alpha^{PV}_{k,t}(\beta^{PV}_{k,l}-\beta^{PV}_{k,t}))$
corresponds to the estimated lower limit of the PV uncertainty interval for
time slot $k$, made at time slot $l$. Note that instead of using the long-term
forecast made at time 0 as the basis for the improvement factors $\beta$, we
use the most recent forecast from time slot $t$, which may already improve
upon the forecast made at time slot $0$. To account for that, we subtract the
improvement factor $\beta^{PV}_{k,t}$ at time $t$, resulting in an updated
improvement factor of $(\beta^{PV}_{k,l}-\beta^{PV}_{k,t})$. Hence, the lower
limit of the PV uncertainty interval is based on the most recent lower limit
estimation from time slot $t$, but adjusted for the average reduction factor.
Using equation (16) and $0\leq\beta_{k,t}<\beta_{k,l}\leq 1$, we have
$c_{t_{l},l}\geq 0$ for $l>t$.

    3. 3.

For arcs $(t,l)$ with $t<l$, we use the current prediction of time slot $t$
and assume average realizations for future time slots

$\begin{split}c_{t,l}=&\sum_{k=l}^{|\mathcal{T}|}\big{(}p^{PV}_{k,t}(1-\alpha^{PV}_{k,t}+\alpha^{PV}_{k,t}(\beta^{PV}_{k,l}-\beta^{PV}_{k,t}))-p^{PV}_{k,t}(1-\alpha^{PV}_{k,t})\big{)}\\\
=&\sum_{k=l}^{|\mathcal{T}|}\big{(}p^{PV}_{k,t}\alpha^{PV}_{k,t}(\beta^{PV}_{k,l}-\beta^{PV}_{k,t})\big{)}.\end{split}$
(23)

    4. 4.

For the remaining arcs $(s,l)$, with $t<s<l$, we again assume the average
realizations of the AR approach. That is, we use the current forecast at time
slot $t$ for future time slots $k$ to compute how large the improvement of
starting an iteration at time slot $l$ is over time slot $s$. Hence, for time
slots $t\leq s<l$ we have

$c_{s,l}=\sum_{k=l}^{|\mathcal{T}|}p^{PV}_{k,t}\alpha^{PV}_{k,t}\big{(}\beta^{PV}_{k,l}-\beta^{PV}_{k,s}\big{)}.$
(24)

For all three approaches, let $\mathcal{M}$ be defined as the set of time
slots, in which the decisions regarding the day-ahead market need to be
submitted. Within this setting, these time slots are 12 pm every day. Note
that also the observations of the uncertain EV demand could be used within the
values and thresholds of the online algorithms, as done in [25]. We refrain
from including the EV demand in the threshold valuation design as the
realizations of EV demand are not time-critical.

##  5 Numerical Results and Analysis

In this section, we test, analyze and discuss the various online scheduling
approaches, presented in Section 3. We first introduce the simulation setting
and then proceed with the analysis of the online threshold algorithm. We
deliberately focus only on the online algorithm without the underlying robust
energy management approach, as introduced in Section 3 to gain insights into
the working of the proposed algorithms. We start with a detailed analysis of
the impact of the threshold on the solution of the basic online threshold
algorithm and then analyze the impact of the various parameter choices. Based
on these results, we propose and further test only selected parameter
combinations for the case of including the robust energy management approach.

###  5.1 Simulation

The simulations are all based on a microgrid of 20 households, equipped with
17 PV systems, 15 EVs and one jointly used battery system. The considered time
horizon spans 3 days and consists of 288 time slots of 15 minutes.

####  5.1.1 Data

To model the household load, we use average Dutch load profiles from the 12th
to the 14th of April 2021 [38]. These profiles are scaled to a household with
a yearly demand of 3,500 kWh, which results in a daily consumption of 8 to 10
kWh per household. All PV systems are modeled equal, with a production of up
to 11 kWh per day. The generation profile is based on a sunny day. The EVs are
based on the VW ID.3, with a battery capacity of 58 kWh and charging and
discharging limits of 11 kW. The charging and discharging efficiencies are
assumed to be 95%. The EV demand is computed based on daily trips between 20
and 70 km and an electricity usage of 18 kWh / 100 km. The jointly used
battery system consists of 3 interconnected Tesla Powerwall modules with an
aggregated battery capacity of 42 kWh [53]. The charging and discharging power
limits are 15 kW, and the efficiencies are again set to 95%. W.l.o.g., we
assume that the initial SoC of EVs and the battery is 0. The day-ahead
electricity prices for the considered time horizon are taken from [16], while
the intraday market prices are taken from the Dutch TSO TenneT [52].

####  5.1.2 Uncertainty Sets

The used parameters for the considered uncertainty, as introduced in Section
4, are:

  * •

The household load uncertainty is defined as $\alpha^{L}=0.2$.

  * •

The EV demand uncertainty is $\alpha^{EV}=0.1$.

  * •

The uncertainty of the electricity prices is $\alpha^{DA}=0.15$ for the day-
ahead market and $\alpha^{ID}=0.35$ for the intraday market.

  * •

The long-term forecast uncertainty for the PV generation is equal to
$\alpha^{PV}=0.25$, but there is a reduction in uncertainty for short-term
forecasts. Within this work, we assume that the uncertainty interval predicted
at time slot $t-s$ for the generation at time slot $t$ is given by

$\left[p^{PV}_{t,t-s}(1-\alpha^{PV}_{t,t-s}),p^{PV}_{t,t-s}(1+\alpha^{PV}_{t,t-s})\right].$
(25)

Hereby, $\alpha^{PV}_{t,t-s}$ reduces by a fixed percentage the smaller $s$
gets, as already described in Section 4. This reduction ranges from 0% for
$s>8$, over 1% for $s=8$ to nearly 70% for $s=0$. This implies that the
uncertainty of the forecast for the coming time slot has decreased by around
70% compared to the initial long-term forecast.

####  5.1.3 Uncertainty Realizations

Next to the time dependency of some uncertainty sets, another important factor
in the evaluation of the algorithms is the underlying probability distribution
of the uncertainty realizations. In most literature on robust optimization, a
uniform distribution is used to draw the actual realizations (see e.g., [4],
[3]). Such a uniform distribution seems to be matching best with the
assumption of having no further knowledge on the underlying distribution apart
from the support. Unless mentioned otherwise, the realizations within this
work are all drawn from a uniform distribution on the interval
$\left[-1,1\right]$.

While the usage of a uniform distribution is common in the context of robust
optimization, in practice, error realizations do not always follow a uniform
distribution. A very popular choice is the normal distribution (see e.g.,
[55], [51], [60]). We use a truncated normal distribution on the interval
$\left[-1,1\right]$ with mean 0 and standard deviation 0.4 to model the
realizations for the PV uncertainty. We stick to the uniform distribution for
the remaining uncertain parameters to better identify, how well the online
scheduling approach works for different uncertainty distributions.

To also be able to analyze the performance of the online (and dynamic)
algorithms under a non-zero mean error distribution, we also consider a
truncated normal distribution with a shifted mean for the PV generation. Note,
that the term non-zero mean does not imply that the forecasts of PV are off,
but that the uncertainty is asymmetrically distributed around the predicted
value. This may reflect that forecasting algorithms are able to predict the PV
generation quite well if there are no clouds, but if there are a few clouds,
which may block direct irradiation for short time periods, this will lead to
larger (negative) deviations from the predicted value. Concisely, the
uncertain PV generation is assumed to be given by a shifted normal
distribution with a mean of 0.6 and a standard deviation of 0.4.

###  5.2 Analysis Online Threshold Algorithms

In this section, we focus on the analysis of the online threshold algorithms
without the underlying robust energy management approach. This implies that we
only use the information gains, as defined in Section 4.2. We first test the
impact of the threshold on the outcome of the online threshold algorithms,
before analyzing the impact of the various individual parameter choices, such
as the percentiles, the factor, or the different approaches presented in
Section 3.

####  5.2.1 Threshold

We focus on the impact of the threshold on the outcome of a basic online
threshold algorithm with a constant threshold. We do not yet analyze the
impact of the various parameters on the results of the algorithms but rather
show how the online threshold algorithm works and how we can evaluate and
compare its performance.

We start with a visual representation of the achieved results of the constant
threshold-based online algorithm. Figure 3 displays the development of the
contribution per time slot (see Equation (19)), for one day based on a
constant threshold. The individual contribution represents the additional PV
generation, which can be used due to improved PV forecasts compared to the
start of the last iteration. The figure also shows the used threshold as well
as the chosen starting time slots. As can be seen, the algorithm starts an
iteration whenever it exceeds the threshold and therefore works as intended.
However, this may change if the threshold takes more extreme values. Figure 4
shows that if the threshold is too low, all iterations are used but are
distributed very early during the day, whereas for a higher threshold, the
starting time slots are distributed more evenly during the day, but do not use
all possible iterations. As iterations starting very early or late during the
day are likely to achieve smaller contributions, the choice of the threshold
seems to be of great importance to achieve a well-balanced solution, in which
(nearly) all iterations are used, but are also well spread among the time
horizon.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$0$$0.5$$1$$1.5$$2$$2.5$Time slot of
the dayadd. PV $[kWh]$ContributionsFully StaticThresholdStarting Points Figure
3: Contributions per time slot for online approach (constant factor, including
starting times slots) and fully static approach (solves the model only once).
The iteration at time slot 48 is part of the set $\mathcal{M}$ and therefore
ignores the threshold.
$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$0$$0.5$$1$$1.5$$2$$2.5$Time slot of
the dayadd. PV $[kWh]$Low Contri.High Contri.Low ThresholdHigh ThresholdLow
StartsHigh Starts Figure 4: Contributions per time slot for online approach
with low and high constant threshold to demonstrate the impact of the
threshold on the solution

Next to the visual analysis of the starting time slots, we can calculate the
objective value of the online algorithms, given by the sum of collected
contributions. The resulting objective values for the three scenarios in
Figures 3 and 4, confirm the initial intuition. While the threshold displayed
in Figure 3 has an objective value of 20.333 kWh, the thresholds from Figure 4
only achieve an objective of 13.218 kWh (low), respectively 17.256 kWh (high).
Hence, even a small change in the threshold can lead to a large change in the
objective value.

The above comparison gives some insights into which threshold performs better,
but it does not indicate how well the best threshold might perform. For this,
we may use an upper bound on the objective value. Within the area of online
(combinatorial) optimization, often the optimal objective value of the offline
scenario, in which all information is known beforehand, is used as a bound. In
our case, we use the path model with the actual forecasts to compute the
optimal starting time slots of an instance in hindsight. Figure 5 shows the
optimal distribution of starting time slots and the corresponding individual
contributions given the realizations of uncertainty for the considered
instance. The optimal offline objective of the instance is 20.891 kWh, showing
an ’optimality gap’ of less than 2.7% for the threshold used in Figure 3.

Figure 5 also shows that we cannot hope for a constant threshold, which leads
to an optimal solution for all instances. Taking the smallest individual
contribution of the optimal solution as the constant threshold would result in
a solution similar to that of the low threshold presented in Figure 4.
Generalizing this insight implies that there does not exist an optimal convex
threshold policy for the online $k$-edge longest path problem.

$0$$10$$20$$30$$40$$50$$60$$70$$80$$90$$0$$0.5$$1$$1.5$$2$$2.5$Time slot of
the dayadd. PV $[kWh]$OptimalOptStartsConstStarts Figure 5: Contributions of
an optimal solution, with OptStarts denoting the optimal starting time slots
of the rolling horizon, while ConstStarts denotes the time slots, in which the
contribution is larger than the smallest optimal contribution, showing that a
constant threshold policy does not lead to an optimal solution

####  5.2.2 Factor

Although it is not possible to derive an optimal online threshold policy to
our problem, in practice it has been shown that simple online threshold
algorithms often achieve good results (see e.g., [1], [54]). In the following,
we, therefore, test the impact of the factor choice on the outcome of the
online threshold algorithms.

Figure 6 displays the objective values of the online threshold algorithm for
the whole range of percentiles and all factor choices introduced in Section 3
using $k=12$ iterations per day. One key observation of Figure 6 is that the
differences in performance between the various factors grow slightly with the
percentile. As can be seen, the piece-wise constant factor performed best
among all factors (which we also observed for the remaining error
distributions and numbers of iterations not displayed in Figure 6). Therefore,
we restrict our following analysis to the piece-wise constant factor.

$0$$0.2$$0.4$$0.6$$0.8$$1$$5$$10$$15$Percentileadd. PV $[kWh]$ConstantPiece-
Wise ConstantLinearQuadraticExponential Figure 6: Contributions of uniform AR
online threshold algorithms for various factors (marks) and percentiles
(x-axis) for a time horizon of three days with $k=12$ iterations per day.

####  5.2.3 Iterations

Figures 7 \- 9 show the results of the AR and HR approaches for the piece-wise
constant factor for the whole range of percentiles and suitably chosen
iterations for the three underlying error distributions. The displayed number
of maximal iterations per day corresponds to various step sizes of the
classical rolling horizon. Figure 10 displays the results for the PR and
exponential ([58]) approaches for the same distributions and iterations. We
compare the results to the (in hindsight) optimal path solution, denoted by
OptPath.

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$10$$20$$30$Percentileadd. PV $[kWh]$iterations
4iterations 6iterations 8iterations 12iterations 24iterations 48OptPathAR
approachHR apporach Figure 7: Contributions of uniform online threshold
algorithms for the AR and the HR approaches with the piece-wise constant
factor and different numbers of iterations (colors) and percentiles (x-axis)
for a time horizon of three days
$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$10$$20$$30$Percentileadd. PV $[kWh]$ Figure 8:
Contributions of normal online threshold algorithms for the AR and the HR
approaches with different numbers of iterations (colors) and percentiles
(x-axis) for a time horizon of three days. Legend is the same as in Fig. 7.
$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$10$$20$$30$Percentileadd. PV $[kWh]$ Figure 9:
Contributions of shifted online threshold algorithms for the AR and the HR
approaches with different numbers of iterations (colors) and percentiles
(x-axis) for a time horizon of three days, Legend is the same as in Fig. 7.
468122448$0$$10$$20$$30$Iterationsadd. PV $[kWh]$PR Uniformexponential [58]
UniformPR Normalexponential [58] NormalPR Shiftedexponential [58] Shifted
Figure 10: Contributions of PR model and exponential [58] for various numbers
of iterations (4 - 48) and uniform, normal, and shifted error distributions

We first analyze the impact of the maximal number of iterations on the
solutions. Based on the results observed in [25], we expect to see an
improvement in objective value with an increasing number of iterations.
Figures 7 \- 10 confirm this expectation to a large extent. There are only a
few small exceptions to this insight, in particular for extreme percentile
choices. Nevertheless, in general, there is a clear distinction in the
objective value between the different maximal numbers of iterations, also for
the PR approach, see Figure 10. This improvement stems from the additional
number of updated PV forecasts with (possibly) improved lower bounds on the PV
generation and can be observed for all underlying probability distributions.
In addition, it can be observed that the gap towards the optimal solution gets
smaller the more iterations can be started.

####  5.2.4 Percentiles

Focusing on the percentile choice, we notice that for small and large values,
the online threshold algorithms perform much worse, see Figures 7 \- 9. This
can be explained by the resulting threshold values of the extreme percentile
choices. As already mentioned, particularly large or small threshold values
can decrease the performance of the overall online algorithm significantly. A
balanced percentile choice between 0.15 and 0.5 on the other hand ensures a
good performance, although small differences between the underlying
probability distributions and approaches can be observed.

####  5.2.5 Approaches

Comparing the results of the AR, HR, and PR approaches with each other, some
conclusions can be drawn. First of all, there does not seem to be a large
difference between the AR and HR approaches w.r.t. their best objective value.
In particular for the normal distribution (see Figure 8), the two approaches
seem to overlap to a high degree for a percentile larger than 0.2, with the
best results usually achieved by a percentile choice between 0.2 and 0.3. For
the uniform distribution, the results of the AR approach improve with
increasing percentile for few iterations, while for the HR approach, it seems
to be the opposite. For a larger number of iterations, this observation does
not hold any longer, although the AR approach seems to be less sensitive
towards large percentile choices compared to the HR approach, which performs
better for smaller percentile choices. The best percentile choice once again
seems to be within the interval $[0.2,0.3]$ in most cases. For the shifted
normal distribution on the other hand the best percentile choice for the AR
approach mostly changes to a slightly higher value between 0.4 and 0.6. The
only exception is the largest number of iterations, for which a very small
percentile choice performs best. Here, the increased percentiles balance out
the rather neutral guess of average realizations compared to the distribution
mean of 0.4. The HR approach on the other hand is not influenced by the mean
of 0.4, as this information is already present in the historical data.

In contrast to the AR and HR approaches, the PR approach is independent of the
percentile choice. In particular for scenarios with a large number of
iterations, it performs quite well, while for few iterations, it is clearly
outperformed by the AR and HR approaches.

Summarizing, the AR and HR approaches both seem to be sensitive toward the
base threshold, while the factor does not influence the outcome a lot.
Nevertheless, there are small differences between the factors, and the piece-
wise constant factor emerged as the most promising one. The underlying error
distributions do not have a large impact on the outcome of the online
algorithms. The PR approach performed really well for a larger number of
iterations, while some deficits can be observed for a smaller number of
iterations.

###  5.3 Analysis Online Rolling Horizon

Within this section, we investigate whether the insights gained in the
previous section also transfer to the solutions when taking the whole online
rolling horizon-based robust energy management approach into account. In
addition to the objective value, which now represents the electricity costs of
the microgrid, we also consider and discuss the impact of the online scheme on
the local PV usage. We compare the results of the various online algorithms to
the solutions of the starting time slots obtained by the optimal offline path
solution, denoted by OptPath rolling horizon, as well as the classical and the
dynamic rolling horizon versions. We consider various step sizes of the
classical rolling horizon and translate these into the corresponding maximal
number of iterations for the dynamic and online rolling horizon models, e.g.,
a step size of 24 time slots results in 4 iterations per day. For the sake of
clarity, we did not include the objective values of the classical rolling
horizon approach in the figures but still refer to them within the analysis.
Similar to the analysis presented in Section 5.2, we restrict the analysis to
the percentile range $\left[0.15,0.5\right]$ as well as the piece-wise
constant factor.

We start with the results based on uniformly random realizations. Figure 11
shows the objective function values, which represent the electricity costs of
the microgrid, while Figure 12 shows the local PV usage of the solutions. Note
that we did not include the results for the PR or the exponential approach in
the figures, as they usually performed significantly worse than the displayed
approaches. Therefore, we focus our analysis on the AR and HR approaches:

  * •

At first glance, when directly comparing Figures 11 and 12, we already notice
that the results regarding objective function and local PV usage rate seem to
mirror each other to a high level of detail. This once again highlights the
impact of the PV forecasts and generation on the objective value and
strengthens our choice of using the PV forecasts as the underlying measure for
the online algorithms within this application scenario.

  * •

In general, the insights gained during the analysis of the online threshold
algorithms also transfer to the results including the robust energy management
scheme. The number of iterations has a significant impact on the solution,
both regarding costs and local PV usage, and the more often an iteration can
be started, the better the results. The individual percentile choices also
align well with the previous results and in general, there is no clear
difference between the AR and HR approaches, neither w.r.t. the objective
values nor regarding the PV usage. Both perform similarly when considering the
percentiles and iterations.

  * •

Compared to the dynamic rolling horizon solution, the AR and the HR approach
outperform it for suitably chosen percentiles both, in costs, as well as in
local PV usage. The online algorithms achieve results that are up to 50%
better compared to the dynamic rolling horizon results, see Figure 11. The
results of the classical rolling horizon model are not displayed in the
figures, as the objective value is much larger compared to all other
approaches, with improvements of the online algorithms of over 85% compared to
the classical rolling horizon. This also aligns well with the insights from
[25], in which the dynamic rolling horizon also clearly outperformed the
classical version.

  * •

Comparing the AR and HR approaches against the OptPath rolling horizon, which
is based on the optimal offline starting time slots, as presented in the
previous analysis, we notice that the more iterations can be started, the
better the online algorithms perform. In a few cases, the objective values of
the online approaches are even better than the ones of the optimal starting
time slot rolling horizon model. At first glance, this may seem
counterintuitive, as the OptPath model served as a bound of the optimal
solution. However, the online threshold algorithms are solely based on the PV
forecasts, while the underlying robust energy management problem also
considers uncertainties in market prices, or EV and household load. Hence,
different decisions taken during the robust energy management approach
combined with uncertainty in market prices have led to a situation, in which
the optimal starting time slots performed worse than the online starting time
slots. When focusing on the PV usage (see Figure 12), which better represents
the objective of the online threshold algorithms, the optimal starting time
slot rolling horizon model clearly outperforms the online algorithms again.

$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$-1$$0$$1$$2$$3$PercentileCostsDynamic
RHOptPath RHAR approachHR approach Figure 11: Objective value (in costs) of
online algorithms for various numbers of iterations (colors) and percentiles
(x-axis) for a time horizon of three days with uniform uncertainty
distribution. The color scheme is the same as used before (see Fig. 7).
$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$0.8$$0.85$$0.9$PercentilePV usage
[%] Figure 12: PV usage (in %) of online algorithms for various numbers of
iterations (colors) and percentiles (x-axis) for a time horizon of three days
with uniform uncertainty distribution. The color scheme is the same as used
before (see Fig. 7).

The results for the normal (Figure 13), respectively shifted normal
distribution (Figure 14) slightly differ from the uniform results.
Nevertheless, the general insights from the analysis of the online scheduling
algorithms, such as the impact of the number of iterations or the percentile
choice on the objective value or the similarity of the AR and the HR
approaches, are still valid. The main differences to the uniform uncertainty
realizations are the results of the dynamic rolling horizon framework, which
are much better and often outperform the OptPath approach. Nevertheless, for
selected iterations and percentiles, the online algorithms still achieve
better results than the dynamic or OptPath approach (see Figures 13 and 14),
although the improvements are much smaller compared to the uniform
distribution case. The classical rolling horizon results are once again not
displayed as these perform significantly worse than any of the other
considered rolling horizon schemes, with improvements of the online algorithms
of over 80%.

$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$-1$$0$$1$$2$$3$PercentileCosts
Figure 13: Objective value (in costs) of online algorithms for various numbers
of iterations (colors) and percentiles (x-axis) for a time horizon of three
days with normal uncertainty distribution. The color scheme is the same as
used before (see Fig. 7).
$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$-1$$0$$1$$2$$3$PercentileCosts
Figure 14: Objective value (in costs) of online algorithms for various numbers
of iterations (colors) and percentiles (x-axis) for a time horizon of three
days with shifted normal uncertainty distribution. The color scheme is the
same as used before (see Fig. 7).

###  5.4 Discussion

Summarizing the previous analysis of the results, we notice that the online
algorithms clearly outperform the dynamic rolling horizon model for the
uniform distribution, while the results for the normal and shifted normal
distribution are much more similar to each other. The OptPath approach, which
served as an upper bound for the pure online algorithms without the energy
management approach, sometimes achieves worse results than the online or the
dynamic rolling horizon approaches. This can be explained by the additional
uncertainty, such as e.g., uncertain market prices, which are not considered
in the online threshold algorithm. The differences in performance between the
underlying error distributions hint that the online algorithms are
particularly useful in certain scenarios. Within the context of the energy
management approach, the uniform error distribution could be seen as the
representation of a particularly cloudy, but still sunny day, in which PV
forecasts can change drastically within a very short time. Hence, both online
algorithms are able to deal with such fluctuating forecasts much better than
any offline algorithm, highlighting interesting application scenarios.

Another interesting insight from the analysis concerns the similarity between
the AR and the HR approach. Even though the HR approach is based on much more
detailed information in the form of multiple data sets following the same
underlying unknown error distribution, the AR approach performed equally well,
even if the mean of the underlying error distribution does not align with the
zero mean assumption of the AR approach, as can be observed for the shifted
normal distribution. Thus, we are able to design well-performing online
algorithms using only very little additional information.

##  6 Conclusion

The aim of this work was to develop the idea of a tailor-made scheduling
scheme for the starting times of iterations of a rolling horizon even further.
Given the often highly dynamic nature of real-world problems with ever-
changing forecasts, scheduling the iterations of the rolling horizon in an
online fashion seems to be a promising idea. Therefore, we developed an online
scheduling framework for a rolling horizon, inspired by results and insights
from various online optimization problems. We proposed, tested, and analyzed
several online threshold algorithms in a case study concerning an energy
management problem under uncertainty. The results of the online algorithms
meet the expectations and we observed improvements of up to 50% compared to
the offline tailor-made scheduling scheme introduced in [25]. When only
focusing on the online algorithms without the underlying robust energy
management approach, we were able to achieve optimality gaps of less than
2.7%. We also highlighted the importance of a well-chosen threshold and the
effect it can have on the objective value. One key finding is that we do not
need much information on future realizations and uncertainty to design well-
performing, simple online algorithms, which are comparable to approaches that
rely on far more information regarding error distributions. Furthermore, the
online algorithms perform particularly well compared to the offline approaches
in situations with highly fluctuating uncertainty realizations. These are
situations, in which offline approaches tend to perform badly, emphasizing the
importance of an online decision tool to regularly achieve good results.

Based on the results and discussion, several interesting future research
directions arise. In a first step, a more theoretical sensitivity analysis of
the threshold could produce valuable insights for the performance of the
online algorithms. In particular, the connection between the percentiles and
the underlying error distribution could provide valuable insights, which could
be used to design threshold functions, yielding some form of guarantee. A more
applied research direction would be to combine the offline and online
algorithms into one algorithm, which depending on the realizations can switch
between a predetermined iteration schedule and the online decision-making
scheme. Such a combined approach can combine the best of both worlds, with the
insurance to use all possible iterations due to the offline schedule and the
ability to react to unusually good or bad realizations due to the online
decision-making.

## Acknowledgements

This research is supported by the Netherlands Organization for Scientific
Research (NWO) Grant 645.002.001.

## References

  * [1] Nick Arnosti and Will Ma  “Tight guarantees for static threshold policies in the prophet secretary problem”  In _Operations Research_ 0 INFORMS, 2022  DOI: https://doi.org/10.1287/opre.2022.2419
  * [2] Moshe Babaioff, Nicole Immorlica, David Kempe and Robert Kleinberg  “A Knapsack Secretary Problem with Applications”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 16–28
  * [3] X. Bai and W. Qiao  “Robust Optimization for Bidirectional Dispatch Coordination of Large-Scale V2G”  In _IEEE Transactions on Smart Grid_ 6.4, 2015, pp. 1944–1954  DOI: https://doi.org/10.1109/TSG.2015.2396065
  * [4] D. Bertsimas et al.  “Adaptive Robust Optimization for the Security Constrained Unit Commitment Problem”  In _IEEE Transactions on Power Systems_ 28.1, 2013, pp. 52–63  DOI: https://doi.org/10.1109/TPWRS.2012.2205021
  * [5] Domagoj Bradac, Anupam Gupta, Sahil Singla and Goran Zuzic  “Robust Algorithms for the Secretary Problem”  arXiv, 2019  DOI: https://doi.org/10.48550/ARXIV.1911.07352
  * [6] Alessandro Francesco Castelli, Luca Moretti, Giampaolo Manzolini and Emanuele Martelli  “A Robust Rolling-Horizon Algorithm for the Optimal Operation of Multi-energy Systems with Yearly Constraints and Seasonal Storage”  In _30th European Symposium on Computer Aided Process Engineering_ 48, Computer Aided Chemical Engineering  Elsevier, 2020, pp. 1513–1518  DOI: https://doi.org/10.1016/B978-0-12-823377-1.50253-6
  * [7] Chandra Chekuri and Vasilis Livanos  “On submodular prophet inequalities and correlation gap”  In _arXiv preprint arXiv:2107.03662_ , 2021  DOI: https://doi.org/10.48550/arXiv.2107.03662
  * [8] S.-H. Choi, A. Hussain and H.-M. Kim  “Adaptive Robust Optimization-Based Optimal Operation of Microgrids Considering Uncertainties in Arrival and Departure Times of Electric Vehicles”  In _Energies_ 11.10, 2018  DOI: https://doi.org/10.3390/en11102646
  * [9] Young H. Chun and Robert T. Sumichrast  “A rank-based approach to the sequential selection and assignment problem”  In _European Journal of Operational Research_ 174.2, 2006, pp. 1338–1344  DOI: https://doi.org/10.1016/j.ejor.2005.03.040
  * [10] Emily Craparo, Mumtaz Karatas and Dashi I. Singham  “A robust optimization approach to hybrid microgrid operation using ensemble weather forecasts”  In _Applied Energy_ 201, 2017, pp. 135–147  DOI: https://doi.org/10.1016/j.apenergy.2017.05.068
  * [11] Mel T. Devine and Valentin Bertsch  “Examining the benefits of load shedding strategies using a rolling-horizon stochastic mixed complementarity equilibrium model”  In _European Journal of Operational Research_ 267.2, 2018, pp. 643–658  DOI: https://doi.org/10.1016/j.ejor.2017.11.041
  * [12] Evgenii Borisovich Dynkin  “The optimum choice of the instant for stopping a Markov process”  In _Soviet Mathematics_ 4, 1963, pp. 627–629
  * [13] Mahmoud Elkazaz, Mark Sumner and David Thomas  “Energy management system for hybrid PV-wind-battery microgrid using convex programming, model predictive and rolling horizon predictive control with experimental validation”  In _International Journal of Electrical Power & Energy Systems_ 115, 2020, pp. 105483  DOI: https://doi.org/10.1016/j.ijepes.2019.105483
  * [14] Mahmoud Elkazaz, Mark Sumner, Seksak Pholboon and David Thomas  “Microgrid Energy Management Using a Two Stage Rolling Horizon Technique for Controlling an Energy Storage System”  In _2018 7th International Conference on Renewable Energy Research and Applications (ICRERA)_ , 2018, pp. 324–329  DOI: https://doi.org/10.1109/ICRERA.2018.8566761
  * [15] Abdellatif Elmouatamid et al.  “Review of Control and Energy Management Approaches in Micro-Grid Systems”  In _Energies_ 14.1, 2021  DOI: https://doi.org/10.3390/en14010168
  * [16] ENTSO-E  “ _Day Ahead Market Prices_ ” Retrieved from https://transparency.entsoe.eu. Accessed March 24, 2022, 2021
  * [17] Moran Feldman, Ola Svensson and Rico Zenklusen  “Online Contention Resolution Schemes”  In _Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pp. 1014–1033  DOI: https://doi.org/10.1137/1.9781611974331.ch72
  * [18] Yimy E. García Vera, Rodolfo Dufo-López and José L. Bernal-Agustín  “Energy Management in Microgrids with Renewable Energy Sources: A Literature Review”  In _Applied Sciences_ 9.18, 2019  DOI: https://doi.org/10.3390/app9183854
  * [19] Foad Ghadimi, Tarik Aouam, Stefan Haeussler and Reha Uzsoy  “Integrated and hierarchical systems for coordinating order acceptance and release planning”  In _European Journal of Operational Research_ 303.3, 2022, pp. 1277–1289  DOI: https://doi.org/10.1016/j.ejor.2022.03.057
  * [20] Saeed Ghadimi and Warren B. Powell  “Stochastic search for a parametric cost function approximation: Energy storage with rolling forecasts”  In _European Journal of Operational Research_ 312.2, 2024, pp. 641–652  DOI: https://doi.org/10.1016/j.ejor.2023.08.003
  * [21] Vincent Guigues and Claudia Sagastizábal  “The value of rolling-horizon policies for risk-averse hydro-thermal planning”  In _European Journal of Operational Research_ 217.1, 2012, pp. 129–140  DOI: https://doi.org/10.1016/j.ejor.2011.08.017
  * [22] Anupam Gupta, Aaron Roth, Grant Schoenebeck and Kunal Talwar  “Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms”  In _Internet and Network Economics_ Springer, Berlin, Heidelberg, 2010, pp. 246–257  DOI: https://doi.org/10.1007/978-3-642-17572-5“˙20
  * [23] Shuang Han et al.  “Mid-to-long term wind and photovoltaic power generation prediction based on copula function and long short term memory network”  In _Applied Energy_ 239, 2019, pp. 181–191  DOI: https://doi.org/10.1016/j.apenergy.2019.01.193
  * [24] Jens Hönen, Johann L. Hurink and Bert Zwart  “A classification scheme for local energy trading”  In _OR Spectrum_ 45, 2023, pp. 85–118  DOI: https://doi.org/10.1007/s00291-022-00697-6
  * [25] Jens Hönen, Johann L. Hurink and Bert Zwart  “Dynamic Rolling Horizon-Based Robust Energy Management for Microgrids Under Uncertainty”, 2023  arXiv:2307.05154 [eess.SY]
  * [26] Jens Hönen, Johann L. Hurink and Bert Zwart  “Robust Energy Management for a Microgrid”  In _2022 IEEE 7th International Energy Conference (ENERGYCON)_ , 2022, pp. 1–6  DOI: https://doi.org/10.1109/ENERGYCON53164.2022.9830301
  * [27] Haim Kaplan, David Naori and Danny Raz  “Competitive Analysis with a Sample and the Secretary Problem”  In _Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pp. 2082–2095  DOI: https://doi.org/10.1137/1.9781611975994.128
  * [28] Ali Keyvandarian and Ahmed Saif  “Robust optimal sizing of a stand-alone hybrid renewable energy system using dynamic uncertainty sets”  In _Energy Systems_ Springer, 2022, pp. 1–27  DOI: https://doi.org/10.1007/s12667-022-00545-0
  * [29] Ioannis Kougias, Nigel Taylor, Georgia Kakoulaki and Arnulf Jäger-Waldau  “The role of photovoltaics for the European Green Deal and the recovery plan”  In _Renewable and Sustainable Energy Reviews_ 144, 2021, pp. 111017  DOI: https://doi.org/10.1016/j.rser.2021.111017
  * [30] Jose Daniel Lara, Daniel E. Olivares and Claudio A. Cañizares  “Robust Energy Management of Isolated Microgrids”  In _IEEE Systems Journal_ 13.1, 2019, pp. 680–691  DOI: https://doi.org/10.1109/JSYST.2018.2828838
  * [31] Shenglin Li et al.  “A novel rolling optimization strategy considering grid-connected power fluctuations smoothing for renewable energy microgrids”  In _Applied Energy_ 309, 2022, pp. 118441  DOI: https://doi.org/10.1016/j.apenergy.2021.118441
  * [32] Haodong Liu et al.  “Online generalized assignment problem with historical information”  In _Computers & Operations Research_ 149, 2023, pp. 106047  DOI: https://doi.org/10.1016/j.cor.2022.106047
  * [33] Álvaro Lorca and Xu Andy Sun  “Adaptive Robust Optimization With Dynamic Uncertainty Sets for Multi-Period Economic Dispatch Under Significant Wind”  In _IEEE Transactions on Power Systems_ 30.4, 2015, pp. 1702–1713  DOI: https://doi.org/10.1109/TPWRS.2014.2357714
  * [34] Álvaro Lorca and Xu Andy Sun  “Multistage Robust Unit Commitment With Dynamic Uncertainty Sets and Energy Storage”  In _IEEE Transactions on Power Systems_ 32.3, 2017, pp. 1678–1688  DOI: https://doi.org/10.1109/TPWRS.2016.2593422
  * [35] Zhuoxin Lu, Xiaoyuan Xu, Zheng Yan and Mohammad Shahidehpour  “Multistage Robust Optimization of Routing and Scheduling of Mobile Energy Storage in Coupled Transportation and Power Distribution Networks”  In _IEEE Transactions on Transportation Electrification_ 8.2, 2022, pp. 2583–2594  DOI: https://doi.org/10.1109/TTE.2021.3132533
  * [36] Alberto Marchetti-Spaccamela and Carlo Vercellis  “Stochastic on-line knapsack problems”  In _Mathematical Programming_ 68.1-3 Springer, 1995, pp. 73–104  DOI: https://doi.org/10.1007/BF01585758
  * [37] Luca Moretti, Emanuele Martelli and Giampaolo Manzolini  “An efficient robust optimization model for the unit commitment and dispatch of multi-energy systems and microgrids”  In _Applied Energy_ 261, 2020, pp. 113859  DOI: https://doi.org/10.1016/j.apenergy.2019.113859
  * [38] NEDU  “ _Dutch demand profiles_ ” Retrieved from https://www.nedu.nl/documenten/verbruiksprofielen/. Accessed March 24, 2022, 2021
  * [39] Lars Kjær Nielsen, Leo Kroon and Gábor Maróti  “A rolling horizon approach for disruption management of railway rolling stock”  In _European Journal of Operational Research_ 220.2, 2012, pp. 496–509  DOI: https://doi.org/10.1016/j.ejor.2012.01.037
  * [40] Saman Nikkhah et al.  “Optimising Building-to-Building and Building-for-Grid Services Under Uncertainty: A Robust Rolling Horizon Approach”  In _IEEE Transactions on Smart Grid_ 13.2, 2022, pp. 1453–1467  DOI: https://doi.org/10.1109/TSG.2021.3135570
  * [41] Daniel E. Olivares, Claudio A. Cañizares and Mehrdad Kazerani  “A Centralized Energy Management System for Isolated Microgrids”  In _IEEE Transactions on Smart Grid_ 5.4, 2014, pp. 1864–1875  DOI: https://doi.org/10.1109/TSG.2013.2294187
  * [42] Rodrigo Palma-Behnke et al.  “A Microgrid Energy Management System Based on the Rolling Horizon Strategy”  In _IEEE Transactions on Smart Grid_ 4.2, 2013, pp. 996–1006  DOI: https://doi.org/10.1109/TSG.2012.2231440
  * [43] M. Pilz and L. Al-Fagih  “Recent Advances in Local Energy Trading in the Smart Grid Based on Game-Theoretic Approaches”  In _IEEE Transactions on Smart Grid_ 10.2, 2019, pp. 1363–1371  DOI: https://doi.org/10.1109/TSG.2017.2764275
  * [44] Aviad Rubinstein and Sahil Singla  “Combinatorial Prophet Inequalities”  In _Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2017, pp. 1671–1687  DOI: https://doi.org/10.1137/1.9781611974782.110
  * [45] S.M. Sadek, W.A. Omran, M.A.M. Hassan and H.E.A. Talaat  “Adaptive robust energy management for isolated microgrids considering reactive power capabilities of distributed energy resources and reactive power costs”  In _Electric Power Systems Research_ 199, 2021, pp. 107375  DOI: https://doi.org/10.1016/j.epsr.2021.107375
  * [46] Javier Silvente, Georgios M. Kopanos, Vivek Dua and Lazaros G. Papageorgiou  “A rolling horizon approach for optimal management of microgrids under stochastic uncertainty” Energy Systems Engineering  In _Chemical Engineering Research and Design_ 131, 2018, pp. 293–317  DOI: https://doi.org/10.1016/j.cherd.2017.09.013
  * [47] Javier Silvente, Georgios M. Kopanos, Efstratios N. Pistikopoulos and Antonio Espuña  “A rolling horizon optimization framework for the simultaneous energy supply and demand planning in microgrids”  In _Applied Energy_ 155, 2015, pp. 485–501  DOI: https://doi.org/10.1016/j.apenergy.2015.05.090
  * [48] Bo Sun et al.  “Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging”  In _Proc. ACM Meas. Anal. Comput. Syst._ 4.3 New York, NY, USA: Association for Computing Machinery, 2021  DOI: https://doi.org/10.1145/3428336
  * [49] Bo Sun et al.  “The Online Knapsack Problem with Departures”  In _Proc. ACM Meas. Anal. Comput. Syst._ 6.3 New York, NY, USA: Association for Computing Machinery, 2022  DOI: https://doi.org/10.1145/3570618
  * [50] Mohamed S. Taha, Hussein Hassan Abdeltawab and Yasser Abdel-Rady I. Mohamed  “An Online Energy Management System for a Grid-Connected Hybrid Energy Source”  In _IEEE Journal of Emerging and Selected Topics in Power Electronics_ 6.4, 2018, pp. 2015–2030  DOI: https://doi.org/10.1109/JESTPE.2018.2828803
  * [51] Qinliang Tan et al.  “A multi-objective optimization dispatching and adaptability analysis model for wind-PV-thermal-coordinated operations considering comprehensive forecasting error distribution”  In _Journal of Cleaner Production_ 256, 2020, pp. 120407  DOI: https://doi.org/10.1016/j.jclepro.2020.120407
  * [52] Tennet  “ _Intraday Market Prices_ ” Retrieved from https://www.tennet.org/english/operational_management/System_data _relating_processing/settlement_prices/index.aspx. Accessed March 24, 2022, 2021
  * [53] Tesla  “ _Technical parameter Tesla Powerwall_ ” Retrieved from https://www.tesla.com/sites/default/files/pdfs/powerwall/ Powerwall_2_AC_Datasheet_EN_NA.pdf. Accessed on March 24, 2023, 2021
  * [54] Lin Yang et al.  “Competitive Algorithms for Online Multidimensional Knapsack Problems”  In _Proc. ACM Meas. Anal. Comput. Syst._ 5.3 New York, NY, USA: Association for Computing Machinery, 2021  DOI: https://doi.org/10.1145/3491042
  * [55] Yeliz Yoldas, Selcuk Goren, Ahmet Onen and Taha Selim Ustun  “Dynamic rolling horizon control approach for a university campus” 2021 The 8th International Conference on Power and Energy Systems Engineering  In _Energy Reports_ 8, 2022, pp. 1154–1162  DOI: https://doi.org/10.1016/j.egyr.2021.11.146
  * [56] Zijun Zhang, Zongpeng Li and Chuan Wu  “Optimal Posted Prices for Online Cloud Resource Allocation”  In _Proc. ACM Meas. Anal. Comput. Syst._ 1.1 New York, NY, USA: Association for Computing Machinery, 2017  DOI: https://doi.org/10.1145/3084460
  * [57] Zhiming Zhong, Neng Fan and Lei Wu  “A hybrid robust-stochastic optimization approach for day-ahead scheduling of cascaded hydroelectric system in restructured electricity market”  In _European Journal of Operational Research_ 306.2, 2023, pp. 909–926  DOI: https://doi.org/10.1016/j.ejor.2022.06.061
  * [58] Yunhong Zhou, Deeparnab Chakrabarty and Rajan Lukose  “Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems”  In _Proceedings of the 17th International Conference on World Wide Web_ , WWW ’08  Beijing, China: Association for Computing Machinery, 2008, pp. 1243–1244  DOI: https://doi.org/10.1145/1367497.1367747
  * [59] Muhammad Fahad Zia, Elhoussin Elbouchikhi and Mohamed Benbouzid  “Microgrids energy management systems: A critical review on methods, solutions, and prospects”  In _Applied Energy_ 222, 2018, pp. 1033–1055  DOI: https://doi.org/10.1016/j.apenergy.2018.04.103
  * [60] Zakaria Ziadi et al.  “Optimal Voltage Control Using Inverters Interfaced With PV Systems Considering Forecast Error in a Distribution System”  In _IEEE Transactions on Sustainable Energy_ 5.2, 2014, pp. 682–690  DOI: https://doi.org/10.1109/TSTE.2013.2292598
  * [61] Marco Zugno and Antonio J. Conejo  “A robust optimization approach to energy and reserve dispatch in electricity markets”  In _European Journal of Operational Research_ 247.2, 2015, pp. 659–671  DOI: https://doi.org/10.1016/j.ejor.2015.05.081


Physics Letters B, 78(2-3):249–251, Sept. 1978.

[42]
R. Penrose and W. Rindler.
Spinors and space-time. Vol. 1.
Cambridge Monographs on Mathematical Physics. Cambridge University
Press, Cambridge, 1987.
Two-spinor calculus and relativistic fields.

[43]
D. C. Robinson.
A simple proof of the generalization of Israel's theorem.
General Relativity and Gravitation, 8(8):695–698, Aug. 1977.

[44]
P. Scott.
The geometries of $3$-manifolds.
Bull. London Math. Soc., 15(5):401–487, 1983.

[45]
W. Simon.
Characterizations of the Kerr metric.
Gen. Relativity Gravitation, 16(5):465–476, 1984.

[46]
W. Simon.
LETTER TO THE EDITOR: Nuts have no hair.
Classical and Quantum Gravity, 12:L125–L130, Dec. 1995.

[47]
S. Sun and R. Zhang.
Collapsing geometry of hyperkaehler 4-manifolds and applications.
arXiv e-prints, page arXiv:2108.12991, Aug. 2021.

[48]
T. tom Dieck.
Transformation groups, volume 8 of De Gruyter Studies in
Walter de Gruyter & Co., Berlin, 1987.

[49]
B. Weber.
Energy and asymptotics of Ricci-flat 4-manifolds with a Killing
Proc. Amer. Math. Soc., 147(7):3117–3130, 2019.

[50]
S. T. Yau.
Remarks on the group of isometries of a Riemannian manifold.
Topology, 16(3):239–247, 1977.