Submodularity of Storage Placement Optimization in Power Networks

In this paper, we consider the problem of placing energy storage resources in a power network when all storage devices are optimally controlled to minimize system-wide costs. We propose a discrete optimization framework to accurately model heterogeneous storage capital and installation costs as these fixed costs account for the largest cost component in most grid-scale storage projects. Identifying an optimal placement strategy is challenging due to (i) the combinatorial nature of such placement problems, and (ii) the spatial and temporal transfer of energy via transmission lines and distributed storage devices. To develop a scalable near-optimal placement strategy with a performance guarantee, we characterize a tight condition under which the placement value function is submodular by exploiting our duality-based analytical characterization of the optimal cost and prices. The proposed polyhedral analysis of a parametric economic dispatch problem with optimal storage control also leads to a simple but rigorous verification method for submodularity, and a novel insight that the spatio-temporal congestion pattern of a power network is critical to submodularity. A modified greedy algorithm provides a (1 - 1/e)-optimal placement solution and can be extended to obtain risk-aware placement strategies when submodularity is verified.