Accelerating Benders decomposition for short-term hydropower maintenance scheduling

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.