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. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

The maintenance scheduling problem for hydroelectric generators involves uncertainty in water flows and nonlinearity in hydroelectric production, solved using a two-stage stochastic program and parallelized Benders decomposition algorithm. By approximating hydroelectric production with linear inequalities and indicator variables, tailoring and testing various acceleration techniques successfully sped up the algorithm fourfold. Industrial results confirm high scalability of the parallelized Benders implementation in various scenarios.