IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2016038.html
   My bibliography  Save this paper

An Asynchronous Distributed Algorithm for solving Stochastic Unit Commitment

Author

Listed:
  • ARAVENA, Ignacio

    (Université catholique de Louvain, CORE, Belgium)

  • PAPAVASILIOU, Anthony

    (Université catholique de Louvain, CORE, Belgium)

Abstract

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 di erences in run times observed among scenario subproblems, which can result in inetic subgradient methods. The algorithm recovers candidate primal solutions from the solutions of scenario subproblems using recombination 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 and of the Central Western European (CWE) system. The WECC system that we study consist of 130 thermal generators, 182 nodes and 319 lines with hourly resolution and up to 1000 scenarios, while the CWE system consist of 656 thermal generators, 679 nodes and 1073 lines, with quarterly resolution and up to 120 scenarios. When using 10 nodes of the cluster per instance, the algorithm provides solutions that are within 2% of optimality to all problems within 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 up to 84% 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.

Suggested Citation

  • ARAVENA, Ignacio & PAPAVASILIOU, Anthony, 2016. "An Asynchronous Distributed Algorithm for solving Stochastic Unit Commitment," LIDAM Discussion Papers CORE 2016038, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2016038
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2016.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Santiago Cerisola & Álvaro Baíllo & José M. Fernández-López & Andrés Ramos & Ralf Gollmer, 2009. "Stochastic Power Generation Unit Commitment in Electricity Markets: A Novel Formulation and a Comparison of Solution Methods," Operations Research, INFORMS, vol. 57(1), pages 32-46, February.
    2. NESTEROV, Yurii, 2012. "Efficiency of coordinate descent methods on huge-scale optimization problems," LIDAM Reprints CORE 2511, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. PAPAVASILIOU, Anthony & OREN, Shmuel & ROUNTREE, Barry, 2015. "Applying high performance computing to transmissions-consstrained stochastic unit commitment for renewable energy integration," LIDAM Reprints CORE 2679, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Miles Lubin & J. Hall & Cosmin Petra & Mihai Anitescu, 2013. "Parallel distributed-memory simplex for large-scale stochastic LP problems," Computational Optimization and Applications, Springer, vol. 55(3), pages 571-596, July.
    5. Anthony Papavasiliou & Shmuel S. Oren, 2013. "Multiarea Stochastic Unit Commitment for High Wind Penetration in a Transmission Constrained Network," Operations Research, INFORMS, vol. 61(3), pages 578-592, June.
    6. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    7. NESTEROV, Yu., 2005. "Smooth minimization of non-smooth functions," LIDAM Reprints CORE 1819, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. PAPAVASILIOU, Anthony & OREN, Schmuel S., 2013. "Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network," LIDAM Reprints CORE 2500, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Wim Ackooij & Jérôme Malick, 2016. "Decomposition algorithm for large-scale two-stage unit-commitment," Annals of Operations Research, Springer, vol. 238(1), pages 587-613, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Schulze, Tim & Grothey, Andreas & McKinnon, Ken, 2017. "A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 247-259.
    2. De Vos, K. & Stevens, N. & Devolder, O. & Papavasiliou, A. & Hebb, B. & Matthys-Donnadieu, J., 2019. "Dynamic dimensioning approach for operating reserves: Proof of concept in Belgium," Energy Policy, Elsevier, vol. 124(C), pages 272-285.
    3. Trine K. Boomsma, 2019. "Comments on: A comparative study of time aggregation techniques in relation to power capacity-expansion modeling," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(3), pages 406-409, October.
    4. Kai Pan & Yongpei Guan, 2022. "Integrated Stochastic Optimal Self-Scheduling for Two-Settlement Electricity Markets," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1819-1840, May.
    5. Daraeepour, Ali & Patino-Echeverri, Dalia & Conejo, Antonio J., 2019. "Economic and environmental implications of different approaches to hedge against wind production uncertainty in two-settlement electricity markets: A PJM case study," Energy Economics, Elsevier, vol. 80(C), pages 336-354.
    6. Hohl, Cody & Lo Prete, Chiara & Radhakrishnan, Ashish & Webster, Mort, 2023. "Intraday markets, wind integration and uplift payments in a regional U.S. power system," Energy Policy, Elsevier, vol. 175(C).
    7. Melamed, Michal & Ben-Tal, Aharon & Golany, Boaz, 2018. "A multi-period unit commitment problem under a new hybrid uncertainty set for a renewable energy source," Renewable Energy, Elsevier, vol. 118(C), pages 909-917.
    8. Fattahi, Salar & Ashraphijuo, Morteza & Lavaei, Javad & Atamtürk, Alper, 2017. "Conic relaxations of the unit commitment problem," Energy, Elsevier, vol. 134(C), pages 1079-1095.
    9. Jianqiu Huang & Kai Pan & Yongpei Guan, 2021. "Multistage Stochastic Power Generation Scheduling Co-Optimizing Energy and Ancillary Services," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 352-369, January.
    10. Luis Montero & Antonio Bello & Javier Reneses, 2022. "A Review on the Unit Commitment Problem: Approaches, Techniques, and Resolution Methods," Energies, MDPI, vol. 15(4), pages 1-40, February.
    11. Faezeh Akhavizadegan & Lizhi Wang & James McCalley, 2020. "Scenario Selection for Iterative Stochastic Transmission Expansion Planning," Energies, MDPI, vol. 13(5), pages 1-18, March.
    12. Victor M. Zavala & Kibaek Kim & Mihai Anitescu & John Birge, 2017. "A Stochastic Electricity Market Clearing Formulation with Consistent Pricing Properties," Operations Research, INFORMS, vol. 65(3), pages 557-576, June.
    13. Skolfield, J. Kyle & Escobedo, Adolfo R., 2022. "Operations research in optimal power flow: A guide to recent and emerging methodologies and applications," European Journal of Operational Research, Elsevier, vol. 300(2), pages 387-404.
    14. Noori, Ehsan & Khazaei, Ehsan & Tavaro, Mehdi & Bardideh, Farhad, 2019. "Economically Operation of Power Utilities Base on MILP Approach," MPRA Paper 95910, University Library of Munich, Germany.
    15. TAYLOR, Adrien B. & HENDRICKX, Julien M. & François GLINEUR, 2016. "Exact worst-case performance of first-order methods for composite convex optimization," LIDAM Discussion Papers CORE 2016052, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Howard, B. & Waite, M. & Modi, V., 2017. "Current and near-term GHG emissions factors from electricity production for New York State and New York City," Applied Energy, Elsevier, vol. 187(C), pages 255-271.
    17. Abdul Rauf & Mahmoud Kassas & Muhammad Khalid, 2022. "Data-Driven Optimal Battery Storage Sizing for Grid-Connected Hybrid Distributed Generations Considering Solar and Wind Uncertainty," Sustainability, MDPI, vol. 14(17), pages 1-27, September.
    18. Hain, Martin & Kargus, Tobias & Schermeyer, Hans & Uhrig-Homburg, Marliese & Fichtner, Wolf, 2022. "An electricity price modeling framework for renewable-dominant markets," Working Paper Series in Production and Energy 66, Karlsruhe Institute of Technology (KIT), Institute for Industrial Production (IIP).
    19. Munoz, Francisco D. & Pumarino, Bruno J. & Salas, Ignacio A., 2017. "Aiming low and achieving it: A long-term analysis of a renewable policy in Chile," Energy Economics, Elsevier, vol. 65(C), pages 304-314.
    20. Le Cadre, Hélène & Mezghani, Ilyès & Papavasiliou, Anthony, 2019. "A game-theoretic analysis of transmission-distribution system operator coordination," European Journal of Operational Research, Elsevier, vol. 274(1), pages 317-339.

    More about this item

    Keywords

    Asynchronous algorithm; coordinate descent method; high performance computing; stochastic programming; unit commitment;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2016038. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.