The Polyhedral Structure of Energy Storage Operations: Convex Hull and Valid Inequalities
Abstract
Energy storage models rely on complementarity constraints to prevent simultaneous charging and discharging, which turn them into disjunctive, nonconvex programs.
Their linear relaxations, widely used in power system operation and planning, often violate these constraints.
This paper studies the polyhedral structure of the multi-period operational set of a storage unit with conversion losses.
We characterize the extreme points of its convex hull and show that, over any sub-horizon, the maximum energy that can be charged, or discharged, during a subset of periods is a submodular function of that subset, computable by a greedy rule.
This structure yields an exponential family of linear valid inequalities, which we strengthen with the continuous power variables, and for which we establish necessary and sufficient conditions to define facets of the convex hull.
The family contains inequalities that strictly dominate the storage capacity inequalities available in the literature.
We further develop a separation algorithm that computes all the coefficients of a cut in linear time and can be made exact over contiguous sets of periods, together with a lifting procedure for the cuts that fail a facet condition.
In 2000 instances of energy arbitrage with negative prices, the linear relaxation strengthened with the separated cuts returns an optimal schedule, free of simultaneous charging and discharging, in every instance, mostly after a single round of separation, whereas the strongest linear relaxation in the literature charges and discharges simultaneously in 43% to 77% of them.