We present an asynchronous algorithm for solving the stochastic unit commitment (SUC) problem using scenario decomposition. The algorithm is motivated by the scale of problem and significant differences in run times observed among scenario subproblems, which can result in an inefficient use of distributed computing resources by parallel synchronous algorithms. Iterations are performed asynchronously using a block-coordinate subgradient method which allows performing block-coordinate updates using delayed information. We provide convergence guarantees for the asynchronous block-coordinate subgradient descent method based on previous results for incremental subgradient methods and stochastic subgradient methods. The algorithm recovers candidate primal solutions from the solutions of scenario subproblems using re-combination heuristics in parallel to dual iterations.
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 system (WECC, hourly resolution, 130 thermal generators, 182 nodes and 319 lines) with up to 1000 scenarios and of the Central Western European system (CWE, 15-minute resolution, 656 thermal generators, 679 nodes and 1073 lines) with up to 120 scenarios. While using 10 nodes of the cluster per instance, the algorithm is able to provide 2% suboptimal solutions to all problems within operationally acceptable time frames: 47 minutes for WECC and 3 hours, 54 minutes for CWE. Moreover, we find that an equivalent synchronous parallel subgradient algorithm would leave processors idle between 25% and 84% of the time, which further stresses the need for designing asynchronous optimization schemes in order to fully exploit distributed computing.
Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996