Abstract
Prosumers—households that both consume and produce energy—face complex decisions in volatile energy markets. This paper investigates the Prosumer Energy Acquisition Cost Minimization (PEAC-min) problem, focusing on the strategic management of battery storage and grid trading. We identify the computational complexity of various problem settings, proving that while most are efficiently solvable, "exclusive" buying constraints introduce NP-hardness. We present a suite of algorithms, including a combinatorial "Buying Backwards" approach and a specialized dynamic programming method. Our results show these tailored algorithms significantly outperform general-purpose ILP solvers, particularly as time horizons expand.
Introduction
As the global energy landscape transitions toward renewables, individual households are increasingly becoming "prosumers"—entities that both consume energy and generate it, typically via photovoltaic (PV) panels. In modern microgrid environments, these prosumers can trade energy with neighbors or the main grid. However, the inherent volatility of electricity prices and solar generation creates a significant optimization challenge. Prosumers must daily decide how much energy to use, store in batteries, sell, or buy to satisfy demand at the minimum cost over a fixed horizon. This study formalizes this as the Prosumer Energy Acquisition Cost Minimization (PEAC-min) problem.
Problem Variants and Complexity
The researchers categorized PEAC-min into several variants based on two primary factors: the permission to sell energy and the presence of "exclusive" buying constraints. In the exclusive variant, a prosumer must either purchase their entire net demand from the grid or rely entirely on their battery for a given period, reflecting realistic "all-or-nothing" market conditions.
A key insight of this work is identifying the complexity threshold. If energy can be purchased in any fraction, the problem remains polynomial-time solvable. However, the exclusive buying constraint (PEAC-BS-Ex) renders the problem NP-hard, as it can be reduced to a variation of the Knapsack problem.
Algorithmic Framework
To address these challenges, the authors developed several specialized algorithms:
- Buying Backwards Algorithm: A combinatorial algorithm for the general PEAC-min problem. It iterates through time and "looks back" to identify the most cost-effective previous periods to purchase and store energy. The authors proved the constraint matrix for this version is totally unimodular, ensuring efficient polynomial-time solutions.
- Dynamic Programming (DP): For the NP-hard exclusive variants, a DP approach was designed. This was facilitated by a reduction to a new theoretical problem: Temporal Knapsack with Item Copies and Lower and Upper Bounds (TKICLUB).
- Integer Linear Programming (ILP): Standard models were also developed to serve as a baseline for comparison.
Experimental Results
The algorithms were evaluated using simulated data based on German market reports from 2023. Prices were modeled using overlapping Gaussian distributions to capture realistic market fluctuations.
The custom DP algorithm demonstrated superior performance compared to Gurobi, a leading commercial ILP solver. As the time horizon ($n$) increased, Gurobi's runtime grew exponentially, often hitting a 180-second timeout. In contrast, the proposed DP algorithm maintained high efficiency, finishing in seconds even for horizons approaching 600 days.
Conclusion and Future Work
This research provides a rigorous foundation for prosumer energy management. By identifying the battery as a strategic arbitrage tool and mapping the complexity of various market constraints, the authors offer practical tools for cost minimization. Future work will focus on transitioning from this "perfect foresight" offline model to online versions that account for real-time uncertainty in weather and pricing, as well as exploring game-theoretic interactions between multiple strategic prosumers in a shared grid.
Summary updated