An Asynchronous Distributed Algorithm for Solving Stochastic Unit Commitment

Wednesday, September 20, 2017 - 11:00am

Event Calendar Category

Other LIDS Events

Speaker Name

Anthony Papavasiliou

Affiliation

Université catholique de Louvain, Belgium

Building and Room Number

32-D677

Abstract

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.

Biography

Anthony Papavasiliou received a B.S. degree in electrical and computer engineering from the National Technical University of Athens, Athens, Greece, and a Ph.D. degree from the Department of Industrial Engineering and Operations Research at the University of California at Berkeley. He holds the ENGIE Chair at the Université catholique de Louvain in Belgium, and is a faculty member of the Center for Operations Research and Econometrics. His interests are focused on the modeling of energy policy and the application of operations research methods in electric power systems operations and electricity markets.

HOST
Dr. Audun Botterud