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

Jul 16, 2026

Upload by Maeve

Benders decomposition addresses large linear optimization in energy planning by separating a master problem for capacity expansion from multiple operation sub-problems. Standard BD solves all sub-problems each iteration, guaranteeing convergence but potentially increasing runtime. A surrogate-based prioritization strategy estimates sub-problem objectives, evaluates the current error of the cutting-plane estimator, and selects the sub-problem with the largest error. The approach is integrated into sequential and asynchronous BD, uses surrogates for convergence checks, and includes regularization. Benchmarks on an energy planning case show reduced solution time correlating with surrogate accuracy, with geometric interpolation performing best, yielding up to 55% speed-up for ten scenarios and 33% for four; asynchronous gains are less consistent.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages24

Reading Time1 h 0 min

Introduction

Benders Decomposition in energy planning

Contribution

Surrogate-based prioritization of sub-problems for Benders decomposition in energy planning Wanhong Yua , Boyung Jürgensb and Leonard Gökea,c,∗ a Reliability and Risk Engineering, Institute of Energy and Process Engineering, ETH Zurich, 8092, Zurich, Switzerland b Institute of Technical Thermodynamics, RWTH Aachen University, 52062, Aachen, Germany c Energy and Process Systems Engineering, ETH Zurich, 8092, Zurich, Switzerland ARTICLE INFO Keywords: Benders decomposition Surrogate modeling Parallelization OR in energy AB STRACT 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% . 1. Introduction Capacity expansion models are key tools for energy planning, but the transition from fossil fuels to renewable sources challenges established modeling practices (Göke et al., 2023) . Unlike fossil fuels, renewable sources fluctuate across daily, seasonal, and inter-annual scales, requiring models to incorporate higher temporal resolutions and diverse weather scenarios to ensure system reliability (Pfenninger, 2017) . In addition, renewable systems depend on short-and long-term storage to balance fluctuations, imposing dependencies across the modeled time-steps (Sepulveda et al., 2021) . Overall, linear optimization problems in energy planning are growing in size and complexity, making them intractable for off-the-shelf solvers. 1.1. Benders Decomposition in energy planning Benders decomposition (BD) solves linear optimization problems by decomposing the initial problem into a master problem (MP) for capacity expansion in the first stage, and several sub-problems (SPs) for arXiv :2607 .05063v1 [ ee ss . SY] 6 Jul 2026 ∗Corresponding author. ORCID(s): Yu, Jürgens, and Göke: Preprint submitted to Elsevier Page 1 of 24 Surrogate-based prioritization of sub-problems operation in the second stage (Benders, 1962) . Then, the algorithm iteratively determines the optimal value of the complicating variables that connect the MP and SPs by constructing a cutting-plane approximation of the SPs within the MP. Initial applications of BD in energy planning date back to 1988 (Pereira and Pinto, 1991) . However, these applications do not leverage BD to address the challenges arising from renewablesand storage in energy planning. Most previous works omit energy storage and the temporal dependencies it imposes between the different SPs for operation (Lohmann and Rebennack, 2017) . Instead, BD addresses problems that are combinatorially complex due to integer variables (Lara

FAQs

What problem does surrogate-based prioritization improve in Benders decomposition for energy planning?

It targets the runtime cost of standard Benders decomposition, which solves all second-stage sub-problems in every iteration, by prioritizing only selected sub-problems based on surrogate-informed estimates.

How does the method decide which sub-problem to prioritize?

Surrogates estimate each sub-problem’s objective, assess the current error of the cutting-plane estimator, and then prioritize the sub-problem with the largest estimated error.

What do the benchmarks indicate about performance and surrogate accuracy?

Solution-time reduction correlates with surrogate accuracy; geometric interpolation-based surrogates outperform machine learning surrogates and can deliver up to 33% speed-up with four scenarios and 55% with ten scenarios in sequential Benders, while asynchronous performance gains are less clear (average 19%).

Jul 16, 2026

Upload by Maeve