IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v238y2016i1d10.1007_s10479-015-2029-8.html
   My bibliography  Save this article

Decomposition algorithm for large-scale two-stage unit-commitment

Author

Listed:
  • Wim Ackooij

    (EDF R&D, OSIRIS)

  • Jérôme Malick

    (CNRS)

Abstract

Everyday, electricity generation companies submit a generation schedule to the grid operator for the coming day; computing an optimal schedule is called the unit-commitment problem. Generation companies can also occasionally submit changes to the schedule, that can be seen as intra-daily incomplete recourse actions. In this paper, we propose a two-stage formulation of unit-commitment, wherein both the first and second stage problems are full unit-commitment problems. We present a primal-dual decomposition approach to tackle large-scale instances of these two-stage problems. The algorithm makes extensive use of warm-started bundle algorithms, and requires no specific knowledge of the underlying technical constraints. We provide an analysis of the theoretical properties of the algorithm, as well as computational experiments showing the interest of the approach for real-life large-scale unit-commitment instances.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2029-8
    DOI: 10.1007/s10479-015-2029-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-015-2029-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-015-2029-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    2. Antonio Frangioni & Claudio Gentile, 2006. "Solving Nonlinear Single-Unit Commitment Problems with Ramping Constraints," Operations Research, INFORMS, vol. 54(4), pages 767-775, August.
    3. Philpott, A. B. & Craddock, M. & Waterer, H., 2000. "Hydro-electric unit commitment subject to uncertain demand," European Journal of Operational Research, Elsevier, vol. 125(2), pages 410-424, September.
    4. Samer Takriti & Benedikt Krasenbrink & Lilian S.-Y. Wu, 2000. "Incorporating Fuel Constraints and Electricity Spot Prices into the Stochastic Unit Commitment Problem," Operations Research, INFORMS, vol. 48(2), pages 268-280, April.
    5. C. Beltran & F. J. Heredia, 2002. "Unit Commitment by Augmented Lagrangian Relaxation: Testing Two Decomposition Approaches," Journal of Optimization Theory and Applications, Springer, vol. 112(2), pages 295-314, February.
    6. X. M. Hu & D. Ralph, 2004. "Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints," Journal of Optimization Theory and Applications, Springer, vol. 123(2), pages 365-390, November.
    7. Matthias Nowak & Werner Römisch, 2000. "Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty," Annals of Operations Research, Springer, vol. 100(1), pages 251-272, December.
    8. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    9. Qipeng Zheng & Jianhui Wang & Panos Pardalos & Yongpei Guan, 2013. "A decomposition approach to the two-stage stochastic unit commitment problem," Annals of Operations Research, Springer, vol. 210(1), pages 387-410, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. W. Ackooij & A. Frangioni & W. Oliveira, 2016. "Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support," Computational Optimization and Applications, Springer, vol. 65(3), pages 637-669, December.
    2. Alexander Franz & Julia Rieck & Jürgen Zimmermann, 2019. "Fix-and-optimize procedures for solving the long-term unit commitment problem with pumped storages," Annals of Operations Research, Springer, vol. 274(1), pages 241-265, March.
    3. Pedro Borges, 2022. "Cut-sharing across trees and efficient sequential sampling for SDDP with uncertainty in the RHS," Computational Optimization and Applications, Springer, vol. 82(3), pages 617-647, July.
    4. Wim Ackooij & Nicolas Lebbe & Jérôme Malick, 2017. "Regularized decomposition of large scale block-structured robust optimization problems," Computational Management Science, Springer, vol. 14(3), pages 393-421, July.
    5. Clara Lage & Claudia Sagastizábal & Mikhail Solodov, 2019. "Multiplier Stabilization Applied to Two-Stage Stochastic Programs," Journal of Optimization Theory and Applications, Springer, vol. 183(1), pages 158-178, October.
    6. Clara Lage & Claudia Sagastizábal & Mikhail Solodov, 2020. "Multiplier Stabilization Applied to Two-Stage Stochastic Programs," Post-Print halshs-02900862, HAL.
    7. Wim van Ackooij & Welington de Oliveira & Yongjia Song, 2018. "Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 57-70, February.
    8. W. Ackooij & X. Warin, 2020. "On conditional cuts for stochastic dual dynamic programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 173-199, June.
    9. Clara Lage & Claudia Sagastizábal & Mikhail Solodov, 2020. "Multiplier Stabilization Applied to Two-Stage Stochastic Programs," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-02900862, HAL.
    10. Clara Lage & Claudia Sagastizábal & Mikhail Solodov, 2020. "Multiplier Stabilization Applied to Two-Stage Stochastic Programs," Documents de travail du Centre d'Economie de la Sorbonne 20010, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.

    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. 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.
    2. Wim Ackooij, 2014. "Decomposition approaches for block-structured chance-constrained programs with application to hydro-thermal unit commitment," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 80(3), pages 227-253, December.
    3. 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.
    4. Yonghan Feng & Sarah Ryan, 2016. "Solution sensitivity-based scenario reduction for stochastic unit commitment," Computational Management Science, Springer, vol. 13(1), pages 29-62, January.
    5. 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.
    6. 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.
    7. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    8. Schulze, Tim & McKinnon, Ken, 2016. "The value of stochastic programming in day-ahead and intra-day generation unit commitment," Energy, Elsevier, vol. 101(C), pages 592-605.
    9. Riis, Morten & Andersen, Kim Allan, 2005. "Applying the minimax criterion in stochastic recourse programs," European Journal of Operational Research, Elsevier, vol. 165(3), pages 569-584, September.
    10. Philip J. Neame & Andrew B. Philpott & Geoffrey Pritchard, 2003. "Offer Stack Optimization in Electricity Pool Markets," Operations Research, INFORMS, vol. 51(3), pages 397-408, June.
    11. Suvrajeet Sen & Lihua Yu & Talat Genc, 2006. "A Stochastic Programming Approach to Power Portfolio Optimization," Operations Research, INFORMS, vol. 54(1), pages 55-72, February.
    12. Fleten, Stein-Erik & Kristoffersen, Trine Krogh, 2007. "Stochastic programming for optimizing bidding strategies of a Nordic hydropower producer," European Journal of Operational Research, Elsevier, vol. 181(2), pages 916-928, September.
    13. Gruson, Matthieu & Cordeau, Jean-François & Jans, Raf, 2021. "Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure," European Journal of Operational Research, Elsevier, vol. 291(1), pages 206-217.
    14. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    15. Wim Ackooij, 2017. "A comparison of four approaches from stochastic programming for large-scale unit-commitment," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 119-147, March.
    16. Huang, Zhouchun & Zheng, Qipeng Phil, 2020. "A multistage stochastic programming approach for preventive maintenance scheduling of GENCOs with natural gas contract," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1036-1051.
    17. 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.
    18. Kai Pan & Ming Zhao & Chung-Lun Li & Feng Qiu, 2022. "A Polyhedral Study on Fuel-Constrained Unit Commitment," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3309-3324, November.
    19. 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.
    20. N. Edirisinghe & E. Patterson, 2007. "Multi-period stochastic portfolio optimization: Block-separable decomposition," Annals of Operations Research, Springer, vol. 152(1), pages 367-394, July.

    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:spr:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2029-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.