Surrogate-based prioritization of sub-problems for Benders decomposition in energy planning

arXiv (Cornell University)

Abstract

Benders decomposition solves optimization problems by separating the first-stage master problem from one or more second-stage sub-problems. While the standard Benders decomposition solves all sub-problems in each iteration, solving only selected sub-problems still guarantees convergence and can reduce solution time, but raises the question of how to select. In this work, we introduce surrogate-based prioritization of sub-problems. The method leverages surrogates to estimate the sub-problems' objectives, assess the current error of the cutting-plane estimator, and then prioritize the sub-problem with the largest error. We implement surrogate-based prioritization within sequential and asynchronous Benders decomposition. Both these algorithms also leverage the surrogate to trigger convergence checks and implement regularization. Benchmarks for an energy planning problem with a few large sub-problems show that the applied prioritization strategy works. The reduction in solution time correlates with the surrogate's accuracy. In our case, geometric interpolation-based surrogates are more accurate than machine learning methods. As a result, prioritization consistently and significantly outperforms the standard algorithm in sequential Benders decomposition. The speed-up increases with the number of scenarios, reaching 33\% with four scenarios and 55% with ten scenarios. In the case of asynchronous parallelization, the impact on performance is less clear, and the average speed-up from prioritization is 19%.

Authors 3

1. Wanhong Yu

   ETH Zurich · Institute of Energy and Process Engineering

   Affiliation as printed

   Reliability and Risk Engineering , Institute of Energy and Process Engineering , ETH Zurich , 8092 , Zurich , Switzerland

2. Boyung Jürgens Aachen Institute of Technical Thermodynamics

   RWTH Aachen University

   Affiliation as printed

   Institute of Technical Thermodynamics , RWTH Aachen University , 52062 , Aachen , Germany

3. Leonard Göke

   ETH Zurich · Institute of Energy and Process Engineering · SystemsX.ch

   Affiliation as printed

   Energy and Process Systems Engineering , ETH Zurich , 8092 , Zurich , Switzerland

   Reliability and Risk Engineering , Institute of Energy and Process Engineering , ETH Zurich , 8092 , Zurich , Switzerland