A stabilised Benders decomposition with adaptive oracles for large-scale stochastic programming with short-term and long-term uncertainty

Abstract

Benders decomposition with adaptive oracles was proposed to solve large-scale optimisation problems with a column-bounded block-diagonal structure, where subproblems differ only in the right-hand side and cost coefficients. Adaptive Benders reduces computational effort significantly by iteratively building inexact cutting planes and valid upper and lower bounds. However, Adaptive Benders and standard Benders may suffer severe oscillation when solving degenerate models. Therefore, we propose stabilising Adaptive Benders with the level method and adaptively selecting which subproblems to solve each iteration for more accurate information. In addition, we propose a dynamic level method to improve the robustness of stabilised Adaptive Benders by adjusting the level set each iteration. We compare stabilised Adaptive Benders with the unstabilised versions of Adaptive Benders with one subproblem solved per iteration and standard Benders on a multi-region long-term power system investment planning problem with short-term and long-term uncertainty. The problem is formulated as multi-horizon stochastic programming. Four algorithms were implemented to solve linear programming with up to 1 billion variables and 4.5 billion constraints. The computational results show that: (a) for a 1.00% convergence tolerance, the proposed stabilised method is up to 113.7 times faster than standard Benders and 2.1 times faster than unstabilised Adaptive Benders; (b) for a 0.10% convergence tolerance, the proposed stabilised method is up to 45.5 times faster than standard Benders and unstabilised Adaptive Benders cannot solve the largest instance to convergence tolerance due to severe oscillation and (c) dynamic level method makes stabilisation more robust.