A Parallelized Cutting-Plane Algorithm for Computationally Efficient Modelling to Generate Alternatives

Michael Lau, Filippo Pecci, Jesse D. Jenkins · 2025

Read A Parallelized Cutting-Plane Algorithm for Computationally Efficient Modelling to Generate Alternatives by Michael Lau, Filippo Pecci, Jesse D. Jenkins (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26029.txt.

Introduction

Michael Lau, Filippo Pecci, and Jesse D. Jenkins speed up a method that maps the range of good alternatives in large energy system models. Modelling to Generate Alternatives explores many near least cost solutions within a small cost slack, by varying investment choices while keeping operations feasible. Each variant needs a full model solve, and hundreds are typical, which makes detailed models with discrete build and retire choices far too slow by standard methods.

Lau and the team reformulate the problem with a tailored cutting plane method based on Benders decomposition, a split between a master problem and subproblems. Sharing cuts between variants and grouping objectives cut solve times in their tests, opening detailed alternative mapping to larger models.

Catalog record

CREATORMichael Lau, Filippo Pecci, Jesse D. Jenkins
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26029

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Parallelized Cutting-Plane Algorithm for Computationally Efficient Modelling to Generate Alternatives Michael Lau, Filippo Pecci, Jesse D. Jenkins Abstract Contemporary macro-energy systems modelling is characterized by the need to represent strategic and operational decisions with high temporal and spatial resolution and represent discrete investment and retirement decisions. This drive towards greater fidelity, however, conflicts with a simultaneous push towards greater model representation of inherent complexity in decision-making, including methods like Modelling to Generate Alternatives (MGA). MGA aims to map the feasible space of a model within a cost slack by varying investment parameters without changing the operational constraints, a process which frequently requires hundreds of solutions. For large, detailed energy system models this is impossible with traditional methods, leading researchers to reduce complexity with linearized investments and zonal or temporal aggregation. This research presents a new solution method for MGA-type problems using cutting-plane methods based on a tailored reformulation of Bender’s Decomposition. We accelerate the algorithm by sharing cuts between MGA master problems and grouping MGA objectives. We find that our new solution method consistently solves MGA problems times faster and requires less memory than existing monolithic Modelling to Generate Alternatives solution methods on linear problems, enabling rapid computation of a greater number of solutions to highly resolved models. We also show that our novel cutting-plane algorithm enables the solution of very large MGA problems with integer investment decisions. 1 Introduction Capacity expansion models (CEM) are optimization-based models which represent the economic capacity procurement and operations of energy systems for a given time period under different sets of assumptions, including engineering, economic, policy, and availability constraints. These models can be used in a variety of contexts to provide decision support for the planning of energy infrastructure. Examples of these insights can include visualizing the roles different energy technologies play in the energy system or how policy levers change system-wide economic incentives [ 1 , 2 ] . In recent years, the requirements these models must meet have become more demanding. Energy systems are becoming increasingly complex and coupled as electrification creates strong interconnections across sectors, weather-dependent variable renewable resources play a central role, and climate change induces extreme events. Representing these systems accurately results in very large linear or mixed-integer optimization problems, with hundreds of millions variables and constraints, which are computationally intensive [ 3 ] . CEMs are formulated as least-cost optimization problems, which represent likely outcomes of efficient markets and are useful for indicative planning [ 1 , 4 , 5 , 6 , 7 , 8 ] . But least-cost optimization misses the much wider feasible region of near-optimal solutions. Prior work has shown that within a small budget relaxation, CEMs have considerable flexibility to change the composition of resources and/or the location of siting decisions, producing very different impacts along a wide range of outcomes of interest [ 2 , 9 , 10 ] . Furthermore, CEMs often omit preferences or constraints important to specific stakeholders, including land-use preferences (i.e. minimizing culturally significant or biodiverse land usage), equity considerations, or tax revenue. Modelling to Generate Alternatives (MGA) is a method to explore the near-optimal feasible region of a convex optimization problem [ 11 , 12 , 13 , 14 , 15 ] . It has been applied previously in energy systems CEMs to offer a wider range of feasible solutions and explore key trade-offs [ 2 , 16 , 9 , 10 ] . MGA is typically carried out by first solving a least-cost optimization problem, then repeatedly re-optimizing with varying objective vectors, subject to a budget constraint limiting the relative increase in cost compared to the least-cost solution [ 15 ] . The key challenge is that CEMs are already very large-scale, and MGA requires the computation of hundreds of solutions to these large models for a given scenario [ 16 , 15 , 9 ] . Recent work has reduced solution time for least-cost mixed-integer CEMs using Benders decomposition [ 17 , 18 ] . These methods iterate between solving a planning problem and a number of parallelized operational subproblems. Each subproblem optimizes system’s operation over a short period of time (e.g., a week), while the planning problem optimizes investment decisions as well as time-coupling variables that link operation across multiple periods (e.g., weekly CO 2 emission budgets.) At each iteration, the solutions of the parallelized sub-problems are used to generate cuts (i.e., linear inequalities) that are added to the planning problem to improve its approximation of system’s operating costs. Importantly, the validity of cuts generated by a Benders iteration only depends on the formulation of the subproblem. This property offers an opportunity to accelerate MGA in the context of CEMs, where we iteratively re-optimize models that differ only in the master problem. However, MGA problems involve a characteristic, complicating "budget constraint", which ties together planning and operational costs, requiring a tailored decomposition formulation. A substantial body of literature exists on utilizing decomposition methods to efficiently solve multi-objective problems. [ 19 ] apply Benders decomposition to multi-objective electricity distribution problems, utilizing an \epsilon- constraint method to explore the solution space. However, work in [ 19 ] is focused on \epsilon- constraints that consider either planning or operational decisions, not both at the same time. As a result, these constraints can be included either in the planning problem or operational sub-problems within a standard Benders decomposition algorithm. In MGA-type problems, we consider \epsilon- constraints that combine planning and operational decisions, requiring tailored decomposition schemes to deal with the resulting complicating constraints. [ 20 ] applied Benders decomposition to bi-objective supply chain problems but do not make any modifications to a standard Benders Decomposition in the multi-objective setting. Instead, they repeat Benders Decomposition naively while varying the weights between objectives. This approach neither includes MGA’s complicating \epsilon -constraints nor takes advantage of repeated solution problem structure as we do. Additionally, [ 21 ] demonstrated a solution method using Benders decomposition to solve bi-objective linear programs. [ 21 ] rely on a simplex approach which does not scale well to higher numbers of objectives making it unsuitable for MGA. It also does not consider \epsilon -constraints, which are a defining feature of MGA. While Benders decomposition approaches have been shown to work well for standard capacity expansion problems, they have not yet been proven to work for MGA-type problems. Simultaneous to this work, [ 22 ] demonstrate that cutting planes can be used to warm-start repeated solutions of ACOPF problems with variations in input data. Also simultaneous to this work, [ 23 ] introduce a generalized algorithmic concept for extracting alternative solutions from Benders decomposition. They do not provide specific formulations or algorithms applied to MGA-type problems, nor do they provide computational testing. In this paper, we present a parallelizable cutting-plane algorithm for generating alternative, near-optimal solutions for large-scale capacity expansion problems which is faster and requires less memory than traditional monolithic solution methods. Our method decomposes system operation into small operational sub-problems that can be optimized in parallel. We accelerate convergence by sharing cuts between different MGA optimizations and partitioning the MGA space to improve the quality of cut information. We apply and demonstrate these methods on a large-scale, open-source, linear capacity expansion model and show

Read the complete text