Accelerating Benders decomposition for short-term hydropower maintenance scheduling

Jesús A. Rodríguez, Miguel F Anjos, Pascal Cote, Guy Desaulniers

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)240-253
Number of pages48
JournalEuropean Journal of Operational Research
Issue number1
Early online date30 Jun 2020
Publication statusPublished - 16 Feb 2021


Dive into the research topics of 'Accelerating Benders decomposition for short-term hydropower maintenance scheduling'. Together they form a unique fingerprint.

Cite this