The paper “Submodularity of storage placement optimization in power networks,” authored by Junjie Qin, Insoon Yang and Ram Rajagopal, has been accepted to the IEEE Transactions on Automatic Control. A preliminary version of this paper has been selected as a finalist for the Best Student Paper Award at the 55th IEEE Conference on Decision and Control.
Abstract: In this paper, we consider the problem of placing energy storage resources in a power network when all storage de- vices 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.