A stabilised Benders decomposition with adaptive oracles for large-scale stochastic programming with short-term and long-term uncertainty
提出了一种稳定化的自适应Benders分解方法，通过水平方法和动态调整子问题求解来加速大规模随机规划问题的求解，在电力系统投资规划中比标准Benders快上百倍。
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.