IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v289y2021i1p240-253.html
   My bibliography  Save this article

Accelerating Benders decomposition for short-term hydropower maintenance scheduling

Author

Listed:
  • Rodríguez, Jesús A.
  • Anjos, Miguel F.
  • Côté, Pascal
  • Desaulniers, Guy

Abstract

Maintenance of power generators is essential for reliable and efficient electricity production. Because generators under maintenance are typically inactive, optimal planning of maintenance activities must consider the impact of maintenance outages on the system operation. However, in hydropower systems finding a minimum cost maintenance schedule is a challenging optimization problem due to the uncertainty of the water inflows and the nonlinearity of the hydroelectricity production. Motivated by an industrial application problem, we formulate the hydropower maintenance scheduling problem as a two-stage stochastic program, and we implement a parallelized Benders decomposition algorithm for its solution. We obtain convex subproblems by approximating the hydroelectricity production using linear inequalities and indicator variables, which account for the nonlinear effect of the number of active generators in the solution. For speeding up the execution of our decomposition algorithm, we tailor and test seven techniques, including three new applications of special ordered sets, presolve and warm start for Benders acceleration. Given the large number of possible configurations of these acceleration techniques, we illustrate the application of statistical methods and computational experiments to identify the best performing configuration, which achieved a fourfold speedup of the decomposition algorithm. Results in an industrial setting confirm the high scalability on the number of scenarios of our parallelized Benders implementation.

Suggested Citation

  • Rodríguez, Jesús A. & Anjos, Miguel F. & Côté, Pascal & Desaulniers, Guy, 2021. "Accelerating Benders decomposition for short-term hydropower maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 289(1), pages 240-253.
  • Handle: RePEc:eee:ejores:v:289:y:2021:i:1:p:240-253
    DOI: 10.1016/j.ejor.2020.06.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720305841
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.06.041?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. Séguin, Sara & Fleten, Stein-Erik & Côté, Pascal & Pichler, Alois & Audet, Charles, 2017. "Stochastic short-term hydropower planning with inflow scenario trees," European Journal of Operational Research, Elsevier, vol. 259(3), pages 1156-1168.
    2. Gendron, Bernard & Scutellà, Maria Grazia & Garroppo, Rosario G. & Nencioni, Gianfranco & Tavanti, Luca, 2016. "A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks," European Journal of Operational Research, Elsevier, vol. 255(1), pages 151-162.
    3. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    4. Steeger, Gregory & Rebennack, Steffen, 2017. "Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: An application to the strategic bidding problem," European Journal of Operational Research, Elsevier, vol. 257(2), pages 669-686.
    5. Wai Foong & Angus Simpson & Holger Maier & Stephen Stolp, 2008. "Ant colony optimization for power plant maintenance scheduling optimization—a five-station hydropower system," Annals of Operations Research, Springer, vol. 159(1), pages 433-450, March.
    6. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    7. Wolf, Christian & Koberstein, Achim, 2013. "Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method," European Journal of Operational Research, Elsevier, vol. 230(1), pages 143-156.
    8. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    9. Froger, Aurélien & Gendreau, Michel & Mendoza, Jorge E. & Pinson, Éric & Rousseau, Louis-Martin, 2016. "Maintenance scheduling in the electricity industry: A literature review," European Journal of Operational Research, Elsevier, vol. 251(3), pages 695-706.
    10. Canto, Salvador Perez, 2008. "Application of Benders' decomposition to power plant preventive maintenance scheduling," European Journal of Operational Research, Elsevier, vol. 184(2), pages 759-777, January.
    11. Cerisola, Santiago & Latorre, Jesus M. & Ramos, Andres, 2012. "Stochastic dual dynamic programming applied to nonconvex hydrothermal models," European Journal of Operational Research, Elsevier, vol. 218(3), pages 687-697.
    12. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    13. Gauvin, Charles & Delage, Erick & Gendreau, Michel, 2017. "Decision rule approximations for the risk averse reservoir management problem," European Journal of Operational Research, Elsevier, vol. 261(1), pages 317-336.
    14. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, 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. Dillon, Mary & Vauhkonen, Ilmari & Arvas, Mikko & Ihalainen, Jarkko & Vilkkumaa, Eeva & Oliveira, Fabricio, 2023. "Supporting platelet inventory management decisions: What is the effect of extending platelets’ shelf life?," European Journal of Operational Research, Elsevier, vol. 310(2), pages 640-654.
    2. Lei, Kaixuan & Chang, Jianxia & Wang, Yimin & Guo, Aijun & Huang, Mengdi & Xu, Bo, 2022. "Cascade hydropower stations short-term operation for load distribution considering water level synchronous variation," Renewable Energy, Elsevier, vol. 196(C), pages 683-693.
    3. Motta, Vinicius N. & Anjos, Miguel F. & Gendreau, Michel, 2024. "Survey of optimization models for power system operation and expansion planning with demand response," European Journal of Operational Research, Elsevier, vol. 312(2), pages 401-412.

    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. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    2. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    3. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    4. Stephen J. Maher, 2021. "Enhancing large neighbourhood search heuristics for Benders’ decomposition," Journal of Heuristics, Springer, vol. 27(4), pages 615-648, August.
    5. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric, 2022. "Meta partial benders decomposition for the logistics service network design problem," European Journal of Operational Research, Elsevier, vol. 300(2), pages 473-489.
    6. Placido dos Santos, Felipe Silva & Oliveira, Fabricio, 2019. "An enhanced L-Shaped method for optimizing periodic-review inventory control problems modeled via two-stage stochastic programming," European Journal of Operational Research, Elsevier, vol. 275(2), pages 677-693.
    7. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    8. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    9. Qian Zhang & Shuaian Wang & Lu Zhen, 2024. "Yard truck retrofitting and deployment for hazardous material transportation in green ports," Annals of Operations Research, Springer, vol. 343(3), pages 981-1012, December.
    10. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    11. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    12. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    13. Dursun, Pınar & Taşkın, Z. Caner & Altınel, İ. Kuban, 2019. "The determination of optimal treatment plans for Volumetric Modulated Arc Therapy (VMAT)," European Journal of Operational Research, Elsevier, vol. 272(1), pages 372-388.
    14. Michels, Adalberto Sato & Lopes, Thiago Cantos & Magatão, Leandro, 2020. "An exact method with decomposition techniques and combinatorial Benders’ cuts for the type-2 multi-manned assembly line balancing problem," Operations Research Perspectives, Elsevier, vol. 7(C).
    15. Neamatian Monemi, Rahimeh & Gelareh, Shahin & Nagih, Anass & Maculan, Nelson & Danach, Kassem, 2021. "Multi-period hub location problem with serial demands: A case study of humanitarian aids distribution in Lebanon," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    16. Nieto-Isaza, Santiago & Fontaine, Pirmin & Minner, Stefan, 2022. "The value of stochastic crowd resources and strategic location of mini-depots for last-mile delivery: A Benders decomposition approach," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 62-79.
    17. Wakui, Tetsuya & Hashiguchi, Moe & Yokoyama, Ryohei, 2021. "Structural design of distributed energy networks by a hierarchical combination of variable- and constraint-based decomposition methods," Energy, Elsevier, vol. 224(C).
    18. 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.
    19. Attari, Mahdi Yousefi Nejad & Torkayesh, Ali Ebadi, 2018. "Developing benders decomposition algorithm for a green supply chain network of mine industry: Case of Iranian mine industry," Operations Research Perspectives, Elsevier, vol. 5(C), pages 371-382.
    20. Liu, Bingqian & Bissuel, Côme & Courtot, François & Gicquel, Céline & Quadri, Dominique, 2024. "A generalized Benders decomposition approach for the optimal design of a local multi-energy system," European Journal of Operational Research, Elsevier, vol. 318(1), pages 43-54.

    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:eee:ejores:v:289:y:2021:i:1:p:240-253. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.