Approximating the energy storage problem and other continuous dynamic programs

30/06/2015 - 12:00
Room 1.5
Giacomo Nannicini

Abstract:
We study the problem of optimally managing a source of renewable energy connected to the power grid, a battery, and potentially a household or some other form of energy sink. This problem can be naturally cast as a dynamic program. We propose a model for this problem that subsumes other models in the literature, and we analyze its complexity, showing that in the deterministic setting the problem is solvable in polynomial time, but it becomes #P-hard in the stochastic setting. A variant of the problem that is commonly encountered in practice (i.e. the one where selling energy to the power grid is not allowed) admits a Fully Polynomial Time Approximation Scheme ( FPTAS) if the energy levels are discretized; but what about the more natural case where energy is considered a continuous variable? We show that in this case, the problem belongs to a class of convex continuous dynamic programs that admits neither a multiplicative nor an additive approximation. We then show that we can construct a novel type of approximation scheme, where additive and multiplicative approximation are required at the same time but both can be arbitrarily small. We discuss a preliminary computational evaluation of this new type of approximation scheme for continuous convex dynamic programs, showing its potential.