Efficient Cost-Minimization Schemes for Electrical Energy Demand Satisfaction by Prosumers in Microgrids with Battery Storage Capabilities

Laura Codazzi, Gergely Csáji, Matthias Mnich

Abstract

We introduce and study various models for satisfying electrical energy demands of prosumers in a microgrid, while optimizing their costs. Each prosumer has individual demands of electrical energy, which can vary day-by-day, and which they can satisfy by either generating electrical energy through a self-operated mini power plant like a solar panel, through buying from an external energy provider, such as the main grid or by trading with other prosumers. Our models take into account two key aspects motivated by real-life scenarios: first, we consider a daily volatility of prices for buying and selling the energy, and second, the possibility to store the self-generated energy in a battery of finite capacity to be either self-consumed or sold to other prosumers in the future. We provide a thorough complexity analysis, as well as efficient algorithms, so that prosumers can minimize their overall cost over the entire time horizon. As a byproduct, we also solve a new, generalized version of the KNAPSACK problem which may be of independent interest. We complement our theoretical findings by extensive experimental evaluations on realistic data sets.

Introduction

As the global energy landscape shifts toward sustainability, households are increasingly transitioning from passive consumers to "prosumers"—active participants who both produce and consume energy. Equipped with photovoltaic (PV) panels and battery storage, these agents can satisfy their needs through self-generation, local microgrid trading, or the main grid. However, optimizing this process is complex due to the inherent volatility of energy production (weather-dependent) and market prices for buying ($c_t$) and selling ($s_t$).

Problem Formulation: PEAC-min

The core challenge addressed is the Prosumer Energy Acquisition Cost Minimization (PEAC-min) problem. A prosumer must make daily decisions over a fixed time horizon $n$ to minimize total costs while satisfying demand $d_t$ and respecting battery capacity $C$. Key decision variables include the amount of energy to consume immediately, store for later, sell back to the grid, or purchase from external sources.

Complexity and Algorithmic Framework

The study identifies a clear complexity boundary based on the flexibility of purchasing decisions.

The Polynomial Case (PEAC-BS-GENERAL)

In general scenarios where any quantity of energy can be purchased, the problem is polynomial-time solvable. The authors prove that the constraint matrix is totally unimodular, allowing standard linear solvers to find integer solutions efficiently. To optimize further, they developed the "Buying Backwards" algorithm. This $O(n^2)$ combinatorial approach iterates through time, identifying the cheapest historical periods to "buy" energy to fill current deficits without violating past battery capacity constraints.

The NP-Hard Case (PEAC-BS-EX-GEN)

When purchasing is restricted to "all-or-nothing" binary decisions—where a prosumer must either buy their full deficit or rely on stored energy—the problem becomes NP-hard. This variant is modeled as a specialized version of a new temporal knapsack problem, TKICLUB (Temporal Knapsack with Item Copies and Lower and Upper Bounds).

Classification of PEAC problem variants based on complexity and solution algorithms.

Experimental Evaluation

The algorithms were tested using simulated datasets reflecting realistic household variances. Battery capacities were sampled from $U[0, 1000]$, and prices were modeled using overlapping Gaussian distributions to capture market volatility, including rare instances where selling prices exceed buying prices.

Performance Results

For the polynomial variants, the "Buying Backwards" algorithm scales linearly in practice, handling horizons of 10,000 days with ease. In the NP-hard binary variants, the proposed Dynamic Programming (DP) approach significantly outperforms industry-standard Integer Linear Programming (ILP) solvers like Gurobi.

Runtime comparison of the proposed DP algorithm versus ILP for the NP-hard variants.

While generic solvers often timed out on larger instances, the DP algorithm consistently provided optimal solutions in seconds, demonstrating its suitability for real-time Home Energy Management Systems (HEMS).

Conclusion

This research provides a robust framework for prosumer cost minimization. By leveraging strategic storage and efficient algorithms, prosumers can significantly reduce energy bills compared to naive greedy strategies. Future work will focus on relaxing the "perfect forecast" assumption by developing online or stochastic models and incorporating battery degradation costs to better reflect long-term hardware health.

Summary updated

Abstract

We introduce and study various models for satisfying electrical energy demands of prosumers in a microgrid, while optimizing their costs. Each prosumer has individual demands of electrical energy, which can vary day-by-day, and which they can satisfy by either generating electrical energy through a self-operated mini power plant like a solar panel, through buying from an external energy provider, such as the main grid or by trading with other prosumers. Our models take into account two key aspects motivated by real-life scenarios: first, we consider a daily volatility of prices for buying and selling the energy, and second, the possibility to store the self-generated energy in a battery of finite capacity to be either self-consumed or sold to other prosumers in the future. We provide a thorough complexity analysis, as well as efficient algorithms, so that prosumers can minimize their overall cost over the entire time horizon. As a byproduct, we also solve a new, generalized version of the KNAPSACK problem which may be of independent interest. We complement our theoretical findings by extensive experimental evaluations on realistic data sets.
BibTeX
@inproceedings{codazzi2024efficient,
  author = {Laura Codazzi and Gergely Csáji and Matthias Mnich},
  title = {{Efficient Cost-Minimization Schemes for Electrical Energy Demand Satisfaction by Prosumers in Microgrids with Battery Storage Capabilities}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=jJHyT3pHRZ},
}
Figure