An Asynchronous Distributed Algorithm for Solving Stochastic Unit Commitment

We present an asynchronous algorithm for solving the stochastic unit commitment (SUC) problem using decomposition. The algorithm is motivated by large differences in run times observed among subproblems, which can result in inefficient use of distributed computing resources by synchronous parallel algorithms. Dual iterations are performed asynchronously using a block-coordinate subgradient descent method which allows performing block-coordinate updates using delayed information, while candidate primal solutions are recovered from the solutions of scenario subproblems using heuristics. The asynchronous algorithm is implemented in a high-performance computing cluster and we conduct numerical experiments for two-stage SUC instances of the Western Electricity Coordinating Council (WECC) system with up to 1000 scenarios and of the Central Western European (CWE) system with up to 120 scenarios. The algorithm provides solutions to all problems within 2% of optimality in at most 23 minutes for WECC and 98 minutes for CWE, and solutions within 1% of optimality in at most 63 minutes for WECC and 133 minutes for CWE. Moreover, we find that an equivalent synchronous parallel algorithm would leave processors idle up to 80.4% of the time, an observation which underscores the need for designing asynchronous optimization schemes in order to fully exploit distributed computing on real world applications.