Optimal Online Algorithms for Peak-Demand Reduction Maximization with Energy Storage

We assume that the peak demand of a large-power customer may occur in $T$ time slots of an on-peak period, like from $9$ a.m. to $10$ p.m. for a shopping mall (Lepage, 2020). Each time slot corresponds to $15$ or $30$ minutes by the power measurement. Then, we can consider the consumed energy (in kWh) instead of the power demand (in kW).

To investigate the benefit of implementing energy storage, we formulate and study the following Peak-demand Reduction Maximization (PRM) problem,

The objective represents the peak-demand reduction introduced by the energy storage. If there is no storage, the peak usage under the demand profile $\bm{d}$ is $\max_{t\in[T]}d_{t}$. After applying the discharging vector $\bm{\delta}$, we reduce the peak usage to $\max_{t\in[T]}\left(d_{t}-\delta_{t}\right)$. The discharging vector should satisfy the capacity and discharging rate constraints. Moreover, each discharging quantity should not exceed the demand of the corresponding slot. Our goal is to maximize the peak-demand reduction by using energy storage, which directly leads to cost reductions on the peak-demand charge. Most existing studies consider the peak minimization objective, namely, $\min_{\bm{\delta}}\max_{t\in[T]}\left(d_{t}-\delta_{t}\right)$. In contrast, we adopt the peak-demand reduction maximization objective in PRM, because it makes us focus on the benefit brought by the energy storage. We observe that the two objectives are consistent in the offline setting because their summation remains a known constant $\max_{t\in[T]}d_{t}$ under any feasible solution. Notwithstanding, we should differentiate them in the online setting where we lack the information of $\max_{t\in[T]}d_{t}$, let alone when we evaluate online algorithms by competitive ratios. Moreover, in the online setting, we consider the performance guarantee over an uncertainty set of the demand profiles. $\max_{t\in[T]}d_{t}$ is non-constant among different demand profiles. Considering a relative peak-reduction value to $\max_{t\in[T]}d_{t}$ instead of the absolute peak-demand value $\max_{t\in[T]}\left(d_{t}-\delta_{t}\right)$ provides a more fair performance comparison among different demand profiles. To the best of our knowledge, our work is the first to study the peak-demand reduction maximization by online competitive analysis.

Clearly, when the demand profile $\bm{d}$ is known, we can easily solve the PRM problem by linear programming. Moreover, the following proposition states that the offline optimal solution to PRM presents a particular threshold-based structure.

Note that $[x]^{+}\triangleq\max\{x,0\}$. A useful observation is that the optimal solution to PRM, is also optimal for the peak-demand minimization problem with the same constraints. For notational convenience, we respectively use $v(\bm{d})$ and $\sigma(\bm{d})$ to denote the optimal peak usage and the optimal peak-demand reduction after discharging stored energy, namely,

where $\bm{\delta}^{*}$ is the optimal solution to PRM. While solving the offline PRM problem is easy, it is challenging to determine the discharging quantities in real-time without knowing future demands, i.e., in online manner. (Bar-Noy et al., 2008) proposed an optimal competitive online algorithm for the peak minimization, assuming that the original peak usage $\max_{t\in[T]}d_{t}$ is known a priori. However, such an assumption is far from practical. In this paper, we consider a more general model where the prior information on the peak usage comprises the lower and upper demand bounds only. Also, we propose, in the next section, an optimal competitive algorithm for the online PRM problem. Overall, our work complements the literature by considering the peak-demand reduction maximization and not assuming to know the exact value of the original peak usage.

In the online setting, we do not know the exact value of $d_{t}$ until time slot $t$. The empirical information only tells us that $d_{t}\in[\underline{d},\overline{d}]$, for all $t\in[T]$. We denote the set of all possible demand profiles by $\mathcal{D}=\{\bm{d}\in\mathbb{R}^{T}\mid\underline{d}\leq d_{t}\leq\overline{d},\forall t\in[T]\}$. Other prior information includes the storage capacity $(c)$, the maximum discharging limit $\bar{\delta}$, and the time-slot number $(T)$. We present, in Fig. 2, an illustrative flowchart of an online algorithm for PRM.

As mentioned in the introduction, concerning robustness and fairness, CR is a proper measure in online optimization with given resources (Borodin and El-Yaniv, 2005). It quantifies the relative performance between an online algorithm and the offline optimal benchmark. For a maximization problem like PRM, the CR of a deterministic online algorithm $\mathfrak{A}$ is defined as the largest ratio between the objective value under an optimal offline solution and that attained by the algorithm over all possible input sequences (e.g., the demand profiles in PRM), namely,

where $\sigma_{\mathfrak{A}}(\bm{d})$ refers to the objective values of PRM under the online algorithm and the input sequence $\bm{d}$. For a randomized algorithm $\mathfrak{A}$, we can extend the concept of CR by replacing $v_{\mathfrak{A}}(\bm{d})$ with $\mathbf{E}[v_{\mathfrak{A}}(\bm{d})]$, where the expectation is due to the random strategies of the algorithm $\mathfrak{A}$. We always have $CR_{\mathfrak{A}}\geq 1$ and a smaller CR indicates that the algorithm can perform more closely to the offline optimal case. We expect to find the online algorithm with the smallest CR, which is the best possible CR among all online algorithms. The best CR not only verifies the optimal performance of the online algorithm, but also quantifies the essential cost of not knowing the future. In other words, the best CR captures the price of uncertainty in the considered online problem.

In the following, we show that it suffices to focus on deterministic online algorithms for the best CR regarding the online PRM.

The usual practice is to propose an online algorithm and then compute its CR for evaluating the performance. In contrast, we herein ask whether there exists an online algorithm with given CR. This question relates to a useful framework for designing competitive online algorithms, called CR-Pursuit. As the name indicates, the CR-Pursuit algorithmic framework requires us to sequentially make online decisions by “pursuing” a prescribed CR. For a maximization problem and a given CR, each CR-Pursuit algorithm will choose actions to maintain an offline-to-online objective ratio to be no more than the CR, in each decision-making round. Despite the conciseness of the idea, there is no general recipe for pursuing the given CR. The means of designing algorithms under CR-Pursuit is problem-specific, as exemplified in (Lin et al., 2019) and (Yi et al., 2019).

We herein summarize several useful observations regarding the CR-Pursuit framework. First, to maintain the offline-to-online ratio in each decision-making round, we usually need to solve an offline problem according to the observed inputs and implemented actions so far. If the offline version of a considered problem is easier, then it is less challenging to design algorithms under CR-Pursuit. Second, the CR-Pursuit framework generally generates a family of algorithms, each of which is characterized by a specific CR. Clearly, the best algorithm among these is the one with the smallest CR. We wonder whether the best algorithm under CR-Pursuit is optimal among all online algorithms. If so, then the CR-Pursuit framework greatly reduces the search space of optimal online algorithms. Overall, there are three main challenges in designing CR-Pursuit algorithms: finding a proper way to sequentially maintain a given CR, identifying the best CR which can be pursued, and checking whether the best CR under CR-Pursuit is the optimal one among all online algorithms. In the following, we shall tackle these challenges with the online PRM. First of all, we shall devise a collection of online algorithms under the CR-Pursuit framework. Then, we show that the best algorithm among these is also optimal among all online algorithms for PRM. Finally, we attain the best online algorithm for PRM by finding the best possible CR.

Without knowing future inputs, it seems impossible to maintain the offline-to-online objective ratio to be no more than a given ratio. If we do not know the time-slot number $(T)$, we can simply assume that there are no future inputs, as has been done in the existing results (Lin et al., 2019; Yi et al., 2019). However, in the online PRM, we are challenged by the facts that $T$ is known and the future inputs will affect the online and offline optimal peak-demand reductions. As a result, we shall introduce a reference input and adaptively update it at each time slot $t\in[T]$. Specifically, we set the reference input sequence at time slot $t$ as

Clearly, the reference input sequence is a combination of the observed demands until time slot $t$ and the lowest possible future demands, indicating the most optimistic forecast. Given a ratio $\pi$, we shall apply CR-Pursuit framework and maintain the offline-to-online ratio under the reference input sequence $\bm{d}^{t}$ to be more than $\pi$ at each time slot $t\in[T]$. To this end, we design a family of algorithms, each of which is characterized by a prescribed ratio $\pi$ and called pCR-PRM($\pi$). The details of pCR-PRM($\pi$) are given in Algorithm 1. For notational convenience, we use $\bm{\delta}(\pi,\bm{d})$ to denote the output sequence of pCR-PRM($\pi$) under input sequence $\bm{d}$.

Alert readers may put forward two issues. First, pCR-PRM($\pi$) may generate infeasible solutions to PRM. Second, we wonder whether the formula in Algorithm 1 can maintain the offline-to-online objective ratio under $\bm{d}^{t}$ to be no more than $\pi$, for all $t\in[T]$. For the first issue, we give the following definition in terms of feasibility of pCR-PRM algorithms.

We address the second issue by the following lemma.

Therefore, we conclude that pCR-PRM($\pi$) can maintain the given CR $\pi$ if and only if it is feasible. Our goal is to find the smallest $\pi$ such that pCR-PRM($\pi$) is feasible. To this end, we shall first characterize the set of all ratios such that the corresponding pCR-PRM algorithms are feasible. For this purpose, we define an inventory function, which maps a given ratio $\pi$ to the maximum accumulated discharging quantity over all possible demand profiles under pCR-PRM($\pi$):

We show below that the feasibility of pCR-PRM($\pi$) is mainly subject to the inventory constraint.

The following lemma unravels the monotonicity of the inventory function $\Phi(\pi)$.

From Lemma 5, we see that there exists a ratio $\bar{\pi}>1$ such that pCR-PRM($\pi$) is feasible only if $\pi\geq\bar{\pi}$. We shall show that pCR-PRM($\bar{\pi}$) is the best pCR-PRM algorithm. More importantly, the best pCR-PRM algorithm also attains the optimal CR among all online algorithms for PRM, as stated in the following theorem.

The above theorem indicates that the solution to $\Phi(\pi)=c$ characterizes the price of uncertainty regarding the online PRM. To find the best online algorithm for PRM, it suffices to search for the best feasible pCR-PRM algorithm. In the next subsection, we shall show an efficient way to find the best possible CR $\pi^{*}$.

Deriving the analytic expression of $\pi^{*}$ over all the parameters $(c,\bar{\delta},T,\underline{d},\overline{d})$ is attractive but challenging. Instead, we shall explore efficient numerical methods for the best CR $\pi^{*}$. As a unique technical contribution, we show that computing $\pi^{*}$ is not much harder than linear programming. Specifically, we first show that the best CR $\pi^{*}$ is the maximum of an exponential number of linear-fractional programs. Then, we exploit the problem structure and show that only a linear number of such programs are necessary in terms of the time-slot number $T$. Note that we can transform each involved linear-fractional program into an equivalent linear program by the techniques in (Boyd and Vandenberghe, 2004, Section 4.3.2).

Recall the key formula of pCR-PRM($\pi$) and the feasibility condition $\Phi(\pi)\leq c$ of pCR-PRM($\pi$). We conclude that pCR-PRM($\pi$) is feasible if and only if for any nonempty subset $\mathcal{I}$ of the index set $[T]$ and any demand profile $\bm{d}\in\mathcal{D}$, it holds that $\sum_{i\in\mathcal{I}}[d_{i}-\max_{k\in[i]}d_{k}+\sigma(\bm{d}^{i})/\pi]^{+}\leq c$. It follows that

A worst-case input sequence for pCR-PRM($\pi^{*}$) refers to a demand profile $\bm{d}\in\mathcal{D}$, under which the pCR-PRM($\pi^{*}$) algorithm will use up the storage, namely $\sum_{t=1}^{T}\delta(\pi^{*},\bm{d})=c$. Since $\Phi(\pi^{*})=c$, there exists a worst-case input sequence for pCR-PRM($\pi^{*}$). Let $\bm{d}^{*}$ be a worst-case input sequence and $\mathcal{I}^{*}$ be the set $\{i\in[T]\mid\delta_{t}(\pi^{*},\bm{d}^{*})>0\}$. Then, we observe that the equality in Formula (2) holds under the index set $\mathcal{I}^{*}$ and the input sequence $\bm{d}^{*}$. Therefore, we attain the following proposition.

Proposition 7 follows directly from Lemma 5 and Proposition 4. Equipped with Proposition 7, we shall transform the computation of the best CR $\pi^{*}$ into solving a sequence of linear-fractional programs. Before proceeding, we observe that $\sigma(\bm{d})=\max_{t\in[T]}d_{t}-\bm{v}(\bm{d})$ and the largest element in $\bm{d}^{t}$ appears in the first $t$ elements. Moreover, we introduce a useful lemma below.

Next, we shall define a family of linear-fractional programs. Each program is parameterized by a nonempty set $\mathcal{I}\subseteq[T]$ and its optimal objective value gives a lower bound of the best CR $\pi^{*}$:

Now, let us interpret the variables, constraints and objective of CR-Comp($\mathcal{I}$). $m_{i},i\in[T]$ are auxiliary variables corresponding to $\max_{k\in[i]}d_{k}$. More specifically, by Lemma 8 and the constraints on the last line, CR-Comp($\mathcal{I}$) will attain its optimum when $m_{i}=\max_{k\in[i]}d_{k}$, for all $i\in\mathcal{I}$. The remaining constraints of CR-Comp($\mathcal{I}$) are associated with the offline PRM problem solved at each time slot under a pCR-PRM algorithm. Precisely, for each $i\in[T]$, the variable $v_{i}$ and the variables $\delta_{ij},j\in[T]$ are respectively related to the optimal objective value and the optimal solution to PRM under the demand profile $\bm{d}^{i}$. CR-Comp($\mathcal{I}$) will attain its optimum when $v_{i}=v(\bm{d}^{i})$, for all $i\in\mathcal{I}$. Moreover, the objective function of CR-Comp($\mathcal{I}$) corresponds to the left part of Formula (2), noting that $\sigma(\bm{d}^{i})=\max_{k\in[i]}d_{k}-v(\bm{d}^{i})$. With a slight abuse of notation, we also use $\textsf{CR-Comp}(\mathcal{I})$ to denote the optimal objective value of the linear-fractional program. As a whole, by Lemma 8, Proposition 7, and the above analysis, we attain the following proposition.

Thus, by Proposition 7 and Proposition 9, we conclude that the best possible CR $\pi^{*}$ equals $\max_{\mathcal{I}\subset[T]}\textsf{CR-Comp}(\mathcal{I})$. That is to say, we can compute $\pi^{*}$ by solving a collection of linear-fractional programs CR-Comp($\mathcal{I}$). Recall that we can convert CR-Comp($\mathcal{I}$) into an equivalent linear program. Thus, computing $\pi^{*}$ is not much harder than solving a collection of linear programs. Moreover, we can compute these programs in parallel, since none of the $\textsf{CR-Comp}(\mathcal{I})$ programs relies on the solution to another. Nevertheless, a direct application of the above results requires to solve an exponential number of linear programs, which is undesirable. Thus, we are motivated to exploit the structure of pCR-PRM($\pi^{*}$) and exclude as many redundant programs as possible. To this end, we derive the following lemma. It identifies a particular worst-case input sequence for pCR-PRM($\pi^{*}$), which continuously discharge stored energy until using up the capacity.

By Proposition 7, Proposition 9, and Lemma 10, we see that there exists $k\in[T]$ such that $\pi^{*}=\textsf{CR-Comp}([k])$. Thus ,we have the following theorem stating that only a linear number ($T$) of CR-Comp($\mathcal{I}$) programs are necessary for the best possible CR $\pi^{*}$, instead of the exponential number $2^{T}$.

In Fig. 3, we illustrate how the best possible CR $\pi^{*}$ varies as each of the parameters $(c,\bar{\delta},T,\underline{d},\overline{d})$ changes. We observe that the optimal CR $\pi^{*}$ increases as $T$ increases and $c$ decreases. $\pi^{*}$ becomes smaller when $\underline{d}$ and $\overline{d}$ getting closer as it reduces the space of the demand profiles. $\pi^{*}$ is non-decreasing in $\bar{\delta}$. When $\bar{\delta}$ is small, e.g., $\bar{\delta}\leq c/T$, the best reduction for both online and offline is $\bar{\delta}$, and the optimal CR is one.

In the simulation, we consider a scenario where an EV charging station operator uses its storage to reduce its peak demand in a day. We obtain three-month electricity data from an EV charging station in Shenzhen, China. We divide the time into slots with 15-min length and derive the power demand of the charging station at each slot from the data. We then identify the on-peak duration in a day from the data. In particular, we consider a decision period of $T=20$ slots and set the demand bounds as $(\underline{d},\bar{d})=(442.91,1020.10)$ kWh, which are the minimum and maximum demand of the charging station in this three months, respectively.

${\textsf{pCR-PRM}}(\pi^{*})$ and adaptive pCR-PRM We evaluate the performance of these two algorithms under different storage capacities and show the result in Fig. 4. The capacity rate represents the ratio between the storage capacity and the average daily demand of the charging station in the specified on-peak period. The peak reduction refers to the average peak reduction rate, which is the average ratio between the peak reduction achieved by respective algorithms and the original peak demand. For Fig. 4, we observe that all the algorithms perform better as the capacity increases. The adaptive pCR-PRM attains a higher peak reduction as compared with pCR-PRM, which corroborates our theoretical findings in Sec. 5. While with little feature demand information, our online algorithm adaptive pCR-PRM can achieve $59\%\sim 81\%$ of the peak reduction of the offline optimal.

Comparison with Alternatives We mainly compare adaptive pCR-PRM with two catalogs of conceivable alternatives, naive threshold-based algorithms and receding horizon control (RHC) algorithms. We show the results in Fig. 5(a) and Fig. 5(b). In particular, we introduce the alternatives as follows,

1. (1)

   THR_half and THR_avg represent the algorithms that discharging to a threshold at each slot until using up the storage. THR_half sets the threshold as $\left(\underline{d}+\bar{d}\right)/2$, and THR_avg sets the threshold as the average offline optimal peak demand after using the storage.

2. (2)

   Eql_Dis equally distributes the energy storage capacity at each slot. Eql_Per discharges at a constant ratio of the demand at each slot until the capacity is running out, and sets the ratio the same as the capacity rate.

3. (3)

   RHC algorithms assume a look-ahead window of $5$ slots (a quarter of the on-peak duration) in our simulation. At each slot, the RHC algorithms first compute the optimal solution based on the demand in the look-ahead window and their guesses beyond the window. Then, it implements the optimal solution at the current slot and recomputes the optimal at the next slot. RHC_lb, RHC_ub, and RHC_half assume the demand beyond the look-ahead window as $\underline{d}$, $\overline{d}$, and $\left(\underline{d}+\overline{d}\right)/2$, respectively.

From Fig. 5(a), we observe that adaptive pCR-PRM achieves the largest peak-shaving under different capacity rates, with at least $23\%$ improvement against threshold-based algorithms. We observe from the Fig. 5(b) that adaptive pCR-PRM has at least $20\%$ improvement and a relatively small deviation on the peak reduction as compared to the RHC algorithms.

Impact of Discharging Limit We evaluate the performance of adaptive pCR-PRM under different maximum charging rates and compare it with alternatives. The results are shown in Fig. 6. We normalize the discharging rate limit by the upper bound $\bar{d}$ of the demand at a slot. We observe that the adaptive pCR-PRM has close performance under different discharging limits, while the offline optimal achieves greater peak reduction as the discharging limit increases. Without knowing the future demand, adaptive pCR-PRM with a larger charging rate limit may waste more energy at the previously observed peak demand which turns out not to be the peak in the whole period. This prevents adaptive pCR-PRM to obtain higher peak reduction at a larger discharging rate limit. Besides, adaptive pCR-PRM outperforms other alternatives under different charging rate limits.