# Block-Based Multicut Benders Decomposition Algorithm for Transmission and Energy Storage Co-Planning

Authors: Edimar José de Oliveira; Arthur Neves de Paula; Leonardo Willer de Oliveira; Leonardo de Mello Honório
Journal: International Transactions on Electrical Energy Systems
 (2022)

---

## Abstract

This study proposes a block-based multicut Benders decomposition algorithm to solve the co-planning of transmission expansion and energy storage problem in a bi-level approach. The proposal breaks the chronological representative period into multiple subperiods blocks. This division makes it possible to use parallel computation methods to solve each block simultaneously, reducing the simulation time, which allows the use of a more extensive time window to model the variability of random variables of the system, such as wind and load. In the proposed algorithm, the master problem defines the State of Charge (SoC) of the energy storage devices between the blocks and the investment in transmission and energy storage devices. To demonstrate the effectiveness of the proposed method, different sizes of representative periods are evaluated in three test systems: Garver 6-bus, IEEE-RTS 24-bus, and IEEE-118 188-bus. The tests compare the performance of the proposed block-based multicut Benders decomposition algorithm with the usual approach applied in the literature considering Benders decomposition and the complete problem formulated as a Mixed-Integer Linear Programming (MILP) problem.


---

## Body

## 1. Introduction

### 1.1. Motivation

The specialized literature presents techniques to solve the Transmission Expansion Problem (PET) considering storage devices in the transmission network with time windows limited to operating days or weeks [1–9]. This problem occurs because of the need to reduce the size of the optimization problem to make it computationally viable. Models limited to operating days or weeks may be accurate for battery-powered Energy Storage Devices, which typically have a low power-to-energy ratio and can be charged and discharged cyclically within a day. However, other storage technologies such as pumped reservoirs can present much more complex operational characteristics, requiring evaluating their operation throughout the operational year. Some works discuss the need to consider all scenarios of an operative year [10–12].Although all proposals in the literature can be modified to consider the entire operating year [10, 13] instead of representative days, the computational cost increases a lot due to the need to represent the power balance constraint considering the transmission network for the entire planning horizon [14] by using, for instance, linear programming or metaheuristics formulations [15]. To avoid this problem, in the present work, this representation of the transmission network is done in a distributed way through the Benders decomposition and parallel computation. Thus, computers with several processing cores can solve linear programming problems for each operating period in a simultaneous manner.Table1 presents a summary of the main characteristics of the most recent publications that have proposed methodologies for solving transmission and storage devices co-planning that consider the energy balance constraint, which causes temporal coupling between the representative periods. Two types of investment in storage devices were identified in the evaluated models: continuous (C) or binary (B). The investments formulated in binary form allow the allocation of storage devices with pre-established power and energy capacities values. On the other hand, investments formulated with continuous variables optimize the power and energy capacities of storage devices installed precisely. In this sense, we highlight the use of a mixed formulation in [7], where the investment in a storage device is defined by binary variables, assigning a fixed cost, while continuous variables with variable costs define the power and energy capacities.Table 1
Taxonomy of recent publications that propose methodologies for solving co-planning of transmission and storage devices.
ReferenceYearStorage device investimentTime windowPlanning horizonTechnologyUCReliability12017C24 hDBESS✓✗22018B24 hSPHES✗✗32018C24 hSBESS✗✗42018B24 hDBESS, CAES, and PHES✓✗52019B48 hSBESS✗✗62019C24 hSBESS and PHES✓✗72019B and C24 hSBESS✗✗82020C120 hSBESS✓✗92021C24 hSCAES✗✓Proposal2022B8760 hSBESS✗✗Regarding the planning horizon, only two references modeled it dynamically (D) while the vast majority of publications considered only the end of the horizon, that is, in a static approach (S). The evaluated works considered three types of technologies: BESS (Battery Energy Storage Systems), CAES (Compressed Air Energy Systems), and PHES (Pumped Hydro Energy Storage). Reference [4] considers these three types and models the investment in storage devices with binary variables, which facilitates the modeling of the different technologies in a single analysis. Three papers considered Unit Commitment (UC) constraints from the review, and only one study considered the calculation of reliability indexes, which points out potential advances in co-planning formulations of transmission and storage devices.Regarding the representative period used to evaluate storage devices’ chronological operation and consider the historical behavior of generation and load, most studies used a 24-hour time window. Only [5, 8] consider larger windows, of 48 and 120 hours, respectively. Larger windows are a practical bottleneck of the formulations found in the literature since they generate programming problems that demand much computational memory, making them hard to be solved. In these formulations, the entire mathematical modeling of the transmission network needs to be replicated for each hour of the time window, being these replicas linked by energy balance constraints related to the State of Charge (SoC) of storage devices. From Table 1, it is possible to identify the need to propose a formulation capable of considering larger time windows efficiently. Thus, the present work contributes by presenting an innovative mathematical formulation that allows temporal decoupling of the energy balance constraints, enabling the fast and simultaneous solution of the operation subproblems for every representative period in a distributed manner, reducing the simulation time and memory usage.Other studies in specialized literature that are important to the discussion of the present proposal consider transmission investment and the presence of storage, but without the possibility of investment in storage devices, or co-planning of generation and storage devices, as detailed in Section1.2.


### 1.2. Related Works

The recent massive share of non-controllable renewable sources, such as solar and wind power, and the need to reduce greenhouse gas emissions in energy matrices, have resulted in efforts to reduce the curtailment of renewable power due to transmission congestion [16]. Among such measures, the search for tools capable of performing transmission system expansion planning along with energy storage systems has grown in recent years. The works highlight that co-planning reduces the overall investment cost since energy storage systems improve the usage of non-controllable generators by storing energy at times of higher renewable power and lower demand and using the stored energy at times of lower renewable availability and higher demand. Furthermore, if well allocated in the network, storage devices can avoid congestion on transmission lines. All these benefits reduce the required investments in transmission lines.In [17, 18], the co-planning of transmission and storage devices is modeled as a Mixed-Integer Linear Programming (MILP) problem. However, the papers do not consider the energy balance and chronological scenarios, which reduces the accuracy of the analyses as it ignores the dynamic behavior of demand and primary energy sources such as solar and wind. In [9], co-planning is formulated as a MILP problem, taking into account the energy balance constraint and the N-1 security criterion. The energy balance constraint increases the size of the MILP problem since all constraints related to system operation are replicated for every operating period of the considered time horizon. This issue limits the time window length since the simulation time can become intractable depending on the power system’s size. This problem is observed in all references presented in Table 1. As already identified in the previous section, the present work presents an innovative formulation that allows decoupling the operation periods from the MILP problem.In [12], six formulations were evaluated based on the complexity of the modeling of the electrical system: temporal resolution, operation flexibility, and uncertainties in fuel prices. From the studies proposed for the co-planning of the generation and storage devices, disregarding the transmission network, the authors conclude that the higher the modeling complexity, the greater the benefits seen with the inclusion of storage devices in the network since they participate in maximizing the use of storage devices and in the operation flexibility. The study points out the importance of including Unit Commitment (UC) constraints in the expansion planning problem.In [1], the authors propose dynamic co-planning of transmission and storage that takes into account wind and load scenarios across representative days in addition to incorporating UC reserve requirements, optimizing size and location of storage devices, and including modeling to consider battery degradation throughout the dynamic planning, with a 25-year planning horizon with 1-year epochs. In [2], a hybrid solution method is proposed that takes into account long-term uncertainties by using robust sets and short-term uncertainties modeled via representative days. Similarly, [5] proposes a stochastic and robust approach to the problem of co-planning transmission and storage devices and models the time series via Bernstein polynomials in order to consider a continuous time instead of the conventional hourly representation. Similarly, [19] uses Bernstein polynomials to demonstrate the advantages of considering continuous time in optimizing the allocation and sizing of fast-acting storage devices. It demonstrates how these devices can assist the operation with their high ramping capability. However, the study in [19] does not consider transmission investments.In [3], the authors formulate a co-planning methodology using the Column-and-Constraint Generation method to solve the MILP model taking into account marketing issues. The subproblem in [3] is modeled as a large linear programming (LP) problem, demanding much computational memory to represent long-time windows. On the other hand, the present work proposes a new methodology capable of dividing this large LP into several LPs that can be solved in an isolated and simultaneous way, with the possibility of considering a one-year window without demanding relatively large amounts of computational memory.In [4], the authors use the Nested Benders decomposition to solve the multi-stage co-planning of transmission and storage devices to consider long-term uncertainties and the investment in diverse types of storage technologies and transmission lines having different construction times. In [6], the co-planning problem is modeled as a MILP solved via Benders decomposition. The authors consider the N-1 security criterion and evaluate the positive impact of including storage devices in the scenarios under contingency. In [7], co-planning is solved by considering robust steps via column-and-constraint generation algorithm. The authors consider binary variables to model storage devices’ charging/discharging status, resulting in a MILP problem with a massive number of binary variables.In [8], a MILP is formulated to model a co-planning problem of storage devices, thyristor-controlled series compensators (TCSC), and transmission facilities considering a linearized AC network that allows representing the reactive supply by TCSC. The model is solved with Benders decomposition. In [20], representative days are used to model wind behavior and to study the relationship between GENCOs and TSO in the co-optimization problem between generation, transmission, and storage devices. In [21], the authors solve a co-planning problem to determine the optimal capacity of an energy storage device coupled to the wind farm and the capacity of the transmission system that connects the farm to the grid. The analysis is performed considering the point of view of a GENCO, which considers the market perspective and generation uncertainties taking into account scenarios through multicut Benders decomposition.


### 1.3. Paper Contributions

This study presents a novel formulation to solve the co-planning of transmission expansion and storage devices, allowing the decoupling of the planning horizon into several smaller subproblems that can be solved using parallel computing techniques. In addition, the proposed approach effectively solves the co-planning problem considering a time window of 8760 hours. A stop criterion is proposed to reduce the methodology’s simulation time. This study includes the analysis of performance in three systems: the 6-bus Garver test system is used to show the impact of increasing the time window in the co-planning problem; the 24-bus IEEE-RTS test system results show the impact of the proposed stop criterion; the IEEE-118 system is used to demonstrate the advantages of considering the parallel computation and evaluates the proposal performance in the face of a time window of 52 weeks in hourly resolution.


### 1.4. Paper Organization

This study is organized as follows: in Section2, the mathematical formulation of co-planning of transmission and energy storage expansion is presented as a MILP problem; in Section 3, the proposed decomposition method is detailed; in Section 4, the results obtained from the proposed methodology are presented and discussed; Section 5 concludes the paper.


## 1.1. Motivation

The specialized literature presents techniques to solve the Transmission Expansion Problem (PET) considering storage devices in the transmission network with time windows limited to operating days or weeks [1–9]. This problem occurs because of the need to reduce the size of the optimization problem to make it computationally viable. Models limited to operating days or weeks may be accurate for battery-powered Energy Storage Devices, which typically have a low power-to-energy ratio and can be charged and discharged cyclically within a day. However, other storage technologies such as pumped reservoirs can present much more complex operational characteristics, requiring evaluating their operation throughout the operational year. Some works discuss the need to consider all scenarios of an operative year [10–12].Although all proposals in the literature can be modified to consider the entire operating year [10, 13] instead of representative days, the computational cost increases a lot due to the need to represent the power balance constraint considering the transmission network for the entire planning horizon [14] by using, for instance, linear programming or metaheuristics formulations [15]. To avoid this problem, in the present work, this representation of the transmission network is done in a distributed way through the Benders decomposition and parallel computation. Thus, computers with several processing cores can solve linear programming problems for each operating period in a simultaneous manner.Table1 presents a summary of the main characteristics of the most recent publications that have proposed methodologies for solving transmission and storage devices co-planning that consider the energy balance constraint, which causes temporal coupling between the representative periods. Two types of investment in storage devices were identified in the evaluated models: continuous (C) or binary (B). The investments formulated in binary form allow the allocation of storage devices with pre-established power and energy capacities values. On the other hand, investments formulated with continuous variables optimize the power and energy capacities of storage devices installed precisely. In this sense, we highlight the use of a mixed formulation in [7], where the investment in a storage device is defined by binary variables, assigning a fixed cost, while continuous variables with variable costs define the power and energy capacities.Table 1
Taxonomy of recent publications that propose methodologies for solving co-planning of transmission and storage devices.
ReferenceYearStorage device investimentTime windowPlanning horizonTechnologyUCReliability12017C24 hDBESS✓✗22018B24 hSPHES✗✗32018C24 hSBESS✗✗42018B24 hDBESS, CAES, and PHES✓✗52019B48 hSBESS✗✗62019C24 hSBESS and PHES✓✗72019B and C24 hSBESS✗✗82020C120 hSBESS✓✗92021C24 hSCAES✗✓Proposal2022B8760 hSBESS✗✗Regarding the planning horizon, only two references modeled it dynamically (D) while the vast majority of publications considered only the end of the horizon, that is, in a static approach (S). The evaluated works considered three types of technologies: BESS (Battery Energy Storage Systems), CAES (Compressed Air Energy Systems), and PHES (Pumped Hydro Energy Storage). Reference [4] considers these three types and models the investment in storage devices with binary variables, which facilitates the modeling of the different technologies in a single analysis. Three papers considered Unit Commitment (UC) constraints from the review, and only one study considered the calculation of reliability indexes, which points out potential advances in co-planning formulations of transmission and storage devices.Regarding the representative period used to evaluate storage devices’ chronological operation and consider the historical behavior of generation and load, most studies used a 24-hour time window. Only [5, 8] consider larger windows, of 48 and 120 hours, respectively. Larger windows are a practical bottleneck of the formulations found in the literature since they generate programming problems that demand much computational memory, making them hard to be solved. In these formulations, the entire mathematical modeling of the transmission network needs to be replicated for each hour of the time window, being these replicas linked by energy balance constraints related to the State of Charge (SoC) of storage devices. From Table 1, it is possible to identify the need to propose a formulation capable of considering larger time windows efficiently. Thus, the present work contributes by presenting an innovative mathematical formulation that allows temporal decoupling of the energy balance constraints, enabling the fast and simultaneous solution of the operation subproblems for every representative period in a distributed manner, reducing the simulation time and memory usage.Other studies in specialized literature that are important to the discussion of the present proposal consider transmission investment and the presence of storage, but without the possibility of investment in storage devices, or co-planning of generation and storage devices, as detailed in Section1.2.


## 1.2. Related Works

The recent massive share of non-controllable renewable sources, such as solar and wind power, and the need to reduce greenhouse gas emissions in energy matrices, have resulted in efforts to reduce the curtailment of renewable power due to transmission congestion [16]. Among such measures, the search for tools capable of performing transmission system expansion planning along with energy storage systems has grown in recent years. The works highlight that co-planning reduces the overall investment cost since energy storage systems improve the usage of non-controllable generators by storing energy at times of higher renewable power and lower demand and using the stored energy at times of lower renewable availability and higher demand. Furthermore, if well allocated in the network, storage devices can avoid congestion on transmission lines. All these benefits reduce the required investments in transmission lines.In [17, 18], the co-planning of transmission and storage devices is modeled as a Mixed-Integer Linear Programming (MILP) problem. However, the papers do not consider the energy balance and chronological scenarios, which reduces the accuracy of the analyses as it ignores the dynamic behavior of demand and primary energy sources such as solar and wind. In [9], co-planning is formulated as a MILP problem, taking into account the energy balance constraint and the N-1 security criterion. The energy balance constraint increases the size of the MILP problem since all constraints related to system operation are replicated for every operating period of the considered time horizon. This issue limits the time window length since the simulation time can become intractable depending on the power system’s size. This problem is observed in all references presented in Table 1. As already identified in the previous section, the present work presents an innovative formulation that allows decoupling the operation periods from the MILP problem.In [12], six formulations were evaluated based on the complexity of the modeling of the electrical system: temporal resolution, operation flexibility, and uncertainties in fuel prices. From the studies proposed for the co-planning of the generation and storage devices, disregarding the transmission network, the authors conclude that the higher the modeling complexity, the greater the benefits seen with the inclusion of storage devices in the network since they participate in maximizing the use of storage devices and in the operation flexibility. The study points out the importance of including Unit Commitment (UC) constraints in the expansion planning problem.In [1], the authors propose dynamic co-planning of transmission and storage that takes into account wind and load scenarios across representative days in addition to incorporating UC reserve requirements, optimizing size and location of storage devices, and including modeling to consider battery degradation throughout the dynamic planning, with a 25-year planning horizon with 1-year epochs. In [2], a hybrid solution method is proposed that takes into account long-term uncertainties by using robust sets and short-term uncertainties modeled via representative days. Similarly, [5] proposes a stochastic and robust approach to the problem of co-planning transmission and storage devices and models the time series via Bernstein polynomials in order to consider a continuous time instead of the conventional hourly representation. Similarly, [19] uses Bernstein polynomials to demonstrate the advantages of considering continuous time in optimizing the allocation and sizing of fast-acting storage devices. It demonstrates how these devices can assist the operation with their high ramping capability. However, the study in [19] does not consider transmission investments.In [3], the authors formulate a co-planning methodology using the Column-and-Constraint Generation method to solve the MILP model taking into account marketing issues. The subproblem in [3] is modeled as a large linear programming (LP) problem, demanding much computational memory to represent long-time windows. On the other hand, the present work proposes a new methodology capable of dividing this large LP into several LPs that can be solved in an isolated and simultaneous way, with the possibility of considering a one-year window without demanding relatively large amounts of computational memory.In [4], the authors use the Nested Benders decomposition to solve the multi-stage co-planning of transmission and storage devices to consider long-term uncertainties and the investment in diverse types of storage technologies and transmission lines having different construction times. In [6], the co-planning problem is modeled as a MILP solved via Benders decomposition. The authors consider the N-1 security criterion and evaluate the positive impact of including storage devices in the scenarios under contingency. In [7], co-planning is solved by considering robust steps via column-and-constraint generation algorithm. The authors consider binary variables to model storage devices’ charging/discharging status, resulting in a MILP problem with a massive number of binary variables.In [8], a MILP is formulated to model a co-planning problem of storage devices, thyristor-controlled series compensators (TCSC), and transmission facilities considering a linearized AC network that allows representing the reactive supply by TCSC. The model is solved with Benders decomposition. In [20], representative days are used to model wind behavior and to study the relationship between GENCOs and TSO in the co-optimization problem between generation, transmission, and storage devices. In [21], the authors solve a co-planning problem to determine the optimal capacity of an energy storage device coupled to the wind farm and the capacity of the transmission system that connects the farm to the grid. The analysis is performed considering the point of view of a GENCO, which considers the market perspective and generation uncertainties taking into account scenarios through multicut Benders decomposition.


## 1.3. Paper Contributions

This study presents a novel formulation to solve the co-planning of transmission expansion and storage devices, allowing the decoupling of the planning horizon into several smaller subproblems that can be solved using parallel computing techniques. In addition, the proposed approach effectively solves the co-planning problem considering a time window of 8760 hours. A stop criterion is proposed to reduce the methodology’s simulation time. This study includes the analysis of performance in three systems: the 6-bus Garver test system is used to show the impact of increasing the time window in the co-planning problem; the 24-bus IEEE-RTS test system results show the impact of the proposed stop criterion; the IEEE-118 system is used to demonstrate the advantages of considering the parallel computation and evaluates the proposal performance in the face of a time window of 52 weeks in hourly resolution.


## 1.4. Paper Organization

This study is organized as follows: in Section2, the mathematical formulation of co-planning of transmission and energy storage expansion is presented as a MILP problem; in Section 3, the proposed decomposition method is detailed; in Section 4, the results obtained from the proposed methodology are presented and discussed; Section 5 concludes the paper.


## 2. Mathematical Formulation of Co-Planning of Transmission and Energy Storage Expansion

The mathematical formulation of co-planning of transmission line and energy storage can be described by the optimization problem (1)–(18).(1)minχ∑k∈KCCkTIkT+∑y∈YCCyYIyY+∑s∈SΔs∑g∈Gcggpgg,s+∑y∈Ycyypyy,sch+pyy,sdis+pen∑b∈Bslb,s,(2)χ=IT,IY,pg,pych,pydis,sl,f,θ,SoC,subject to(3)∑g∈Gbpgg,s+∑y∈Ybpyy,sch−pyy,sdis−∑k∈Kbfk,s+slb,s+−slb,s−=db,s,∀b∈B,s∈S,(4)fk,s=γkθki,s−θkj,s,∀k∈KE,s∈S,(5)−Mk1−IkT≤fk,s−γkθki,s−θkj,s≤Mk1−IkT,∀k∈KC,s∈S,(6)SoCy,s+1=SoCy,s+Δspyy,sch−pyy,sdis,∀y∈Y,s∈S,(7)0≤SoCy,s≤SoC¯y,∀y∈YE,s∈S,(8)0≤SoCy,s≤IyY⋅SoC¯y,∀y∈YC,s∈S,(9)0≤pgg,s≤pg¯g⋅δg,s,∀g∈G,s∈S,(10)0≤pyy,sch,pyy,sdis≤py¯y,∀y∈YE,s∈S,(11)0≤pyy,sch,pyy,sdis≤IyY⋅py¯y,∀y∈YC,s∈S,(12)fk,s≤f¯k,∀k∈KE,s∈S,(13)fk,s≤IkT⋅f¯k,∀k∈KC,s∈S,(14)0≤slb,s≤db,s,∀b∈B,s∈S,(15)SoCy,s=SoCy,s∗,s=1,ns+1,(16)IyY≤I¯yY,∀y∈YC,(17)IyY∈ℤ,∀y∈YC,(18)IkT∈0,1,∀k∈KC.The objective function (1) aims to minimize the investment costs in transmission lines and storage devices as well as the generation costs. The charge/discharge cost cyy is set as a small value only to avoid the simultaneous charging and discharging of storage device y and the use of binary variables to define its operational state. The penalty pen is used to avoid the use of slack variables introduced to improve the problem convergence process. The set of decision variables ξ is presented in (2), which the variables are represented by a multidimensional array containing all variables of the problem. The active power balance in bus b is formulated in (3). The active power flow in existent and candidate lines are, respectively, calculated in (4) and (5). The variable fk, s is positive if the active power flow flows from bus ki to kj, which are the terminal buses of line k. The reduced disjunctive model [22] is applied in (5) in order to reduce the computational time of solving the MILP problem by reducing the number of binary variables in comparison to the disjunctive model proposed in [23]. The energy balance is modeled in (6) and the SoC level difference between the scenarios s and s+1 is dependent on the duration of scenario s. The energy capabilities for existent and candidate storage devices are respectively defined in (7) and (8). The generation capacity of generator g in scenario s is defined in (9), where the maximum active power generation pg¯g is reduced by the availability factor δg,s which can be used to model the variability of wind and solar generation or the availability of fuels in non-renewable generators. In (9), the renewable spillage is allowed and is calculated when a renewable generator does not deliver all the available active power, i. e., when pgg,s<pg¯g⋅δg,s. The bounds for charging/discharging for the existent and candidate storage devices are respectively defined in (10) and (11). The power flow limits in existent and candidate lines are respectively expressed in (12) and (13). Constraint (14) limits the slack variable. In (15), the SoC level of each storage device is fixed for scenarios 1 and ns+1 where ns is the number of scenarios. It must be stressed that the energy balance is valid for all scenarios, and there are ns+1 SoC levels for each storage device, but with first and last SoC levels are fixed by a user-defined value, which is important to guarantee that, even for a one-scenario analysis, the energy balance is well modeled. In (16) and (17), the investment in storage devices are limited to a maximum value and set as an integer value. Finally, in (18), the investment in transmission is set as a binary variable.As proposed in [24, 25], it is applied (19) to calculate the disjunctive parameter Mk for candidate line k.(19)Mk=2θ¯γk,∀k∈KC.


## 3. Proposed Benders Decomposition-Based Approach

This section presents the proposed decomposition approach based on the multicut Benders’ decomposition method. The method is applied to divide the MILP problem presented in Section2 in several subproblems. As the problem considers storage devices, it also considers temporal aspects, which couple the subproblems represented by scenarios by using the energy balance constraint, formulated in (6). In order to decouple the subproblems and efficiently solve the whole problem, a block-based structure is proposed for the planning horizon to define when each problem variable is solved in the iterative approach based on the Benders’ decomposition method as detailed in Section 3.1.


### 3.1. Block-Based Planning Horizon

Figure1 presents the scenarios (represented by squares) of the representative period grouped into nbl blocks (subperiods of the planning horizon). In the proposed structure, there are three types of scenarios (represented in Figure 1 by different colors) depending on how the SoC of the storage devices is defined in the proposed decomposed formulation:(i)
Yellow Squares. They are the first and the last SoC of storage devices on the planning horizon. These values are the user-defined values of SoCy,s∗ for the storage device y at the scenario s as formulated in constraint (15).(ii)
Purple Squares. They represent the scenarios that belong only to block bl. For these scenarios, the SoC variables are calculated in the correspondent subproblem bl.(iii)
Green Squares. They represent the scenarios shared by two adjacent blocks. The SoC variables are calculated in the Master Problem and formulated as fixed variables in the two correspondent subproblems for these scenarios, which guarantees the continuity of SoC in the representative period as a whole and allows to extract the Lagrange multipliers related to the SoCs variables at the first and last scenarios of each block.Figure 1
Arrangement of the scenarios innbl blocks.Figure1 presents the representative period divided into nbl blocks of scenarios. The index wbl is equivalent to the first scenario of the block Sbl, which ends in the scenario wbl+1−1 as defined in (20). Thus, wbl and wbl+1 are the frontier scenarios of block bl whose SoC levels of storage devices are defined by the master problem and imposed as fixed values for the subproblem bl. The set of all frontier scenarios Γ is defined in (21) and the set of frontier scenarios Γbl for block bl is defined in (22). The relationship between frontier scenarios and scenario indexes is expressed in (23), where nsbl is the number of scenarios in block bl and ns0 is defined as equal to 1. It is important to notice that the last frontier scenario wnbl+1 is equivalent to the scenario nsnbl+1 which is a scenario index only used to fix the SoC level of storage device y at the specified value SoCy,ns+1∗ as defined in (15) at the end of planning horizon.(20)Sbl=wbl,wbl+1,wbl+2,…,wbl+1,(21)Γ=w1,w2,…,wbl,…,wnbl,wnbl+1,(22)Γbl=wbl,wbl+1,(23)wbl=∑bl=0bl−1nsbl.


### 3.2. Master Problem

The master problem is defined in (24)–(29) and it is responsible for defining the SoC of storage devices between each block of representative scenarios and the investment in transmission lines and storage devices.(24)Cmpv=minχmp∑k∈KCCkTIkT+∑y∈YCCyYIyY+∑s∈Γαs,(25)χmp=IT,IY,SoC,α,subject to (7)-(8), considering S=Γ, (16)–(18), and:(26)SoCy,s+1−SoCy,s≤Δbl⋅py¯y,∀y∈YE,s∈Γ,(27)SoCy,s+1−SoCy,s≤Δbl⋅IyY⋅py¯y,∀y∈YC,s∈Γ,(28)Csps,κ−∑y∈Yλy,sSoCκSoCy,s−SoCy,sκ+λy,s+1SoCκSoCy,s+1−SoCy,s+1κ+…−∑y∈YCλy,sYκIyY−IyYκ−∑k∈KCλk,sTκIkT−IkTκ≤αs,∀s∈Γ,κ=1,…,v−1,(29)αs≥0.The objective function in (24) aims to minimize the investment in transmission lines and storage devices. The set of decision variables of the master problem is expressed in (25). In (26)-(27) are imposed auxiliary constraints to the master problem in order to improve the convergence of the method. These constraints limit the SoC values defined for all frontier scenarios at feasible levels that each subproblem solution can achieve. Thus, the distance between the SoC levels in each storage device to a given Γbl needs to be less to its maximum charging/discharging capacity during all block duration. The set of Benders’ cuts is formulated in (28). Finally, αs is set as a non-negative variable in (29).


### 3.3. Subproblems

The subproblems are responsible for evaluating the power system’s operational condition for a subperiod of the planning horizon. The subproblem related to the blockbl is formulated as follows:(30)Cspbl,v=minχ∑s∈SblΔbl∑g∈Gcggpgg,s+∑y∈Ycyypyy,sch+pyy,sdis+pen∑b∈Bslb,s,subject to (3)–(14), considering S=Sbl, and(31)SoCy,s=SoCy,sv,∀y∈Y,s∈Γblλy,sSoC,(32)IyY=IyYv,∀y∈YCλk,blY,(33)IkT=IkTv,∀k∈KCλk,blT,where SoCy,sv=SoCy,s∗fors=1,ns+1The objective function (30) aims to minimize the operational cost of generators by defining the dispatch of generation and use of storage devices along the subperiod defined by the block bl. The constraints (31)–(33) impose the decisions calculated by the master problem at iteration v.


### 3.4. Convergence Criteria

Two convergence criteria are evaluated in this paper as following.


#### 3.4.1. Traditional Benders Decomposition Convergence Criterion

At each iterationv the algorithm computes an upper bound value of the objective function of the original problem with (34) and a lower bound value with (35). If Zupv−Zdnv/Zupv was less than a convergence criteria, e. g., 0.001, stop the iterative approach.(34)Zupv=Cmpv−∑s∈Γαsv+∑s∈SblCspbl,v,(35)Zdnv=Cmpv.where αsv is the calculated value for αs from the optimal solution of master problem at iteration v.


#### 3.4.2. Proposed Convergence Criterion

Since the master problem in the proposed decomposition approach is responsible for investing and allocating the SoCs in the storage devices, a longer iterative process is needed to converge the traditional Benders decomposition convergence criterion. After defining a good expansion alternative, with no load shedding, the Benders decomposition searches for an optimal operational condition for all time windows, which can be hard to achieve. Thus, as demonstrated in the result section, it is proposed to stop the Benders decomposition when an expansion alternative without load shedding is found.The result obtained with this proposed convergence criterion is sub-optimal. However, it can be improved by performing ana posteriori simulation with the investment variables fixed at the solution values, reducing the complexity of the problem drastically since master problems became an LP problem.


## 3.1. Block-Based Planning Horizon

Figure1 presents the scenarios (represented by squares) of the representative period grouped into nbl blocks (subperiods of the planning horizon). In the proposed structure, there are three types of scenarios (represented in Figure 1 by different colors) depending on how the SoC of the storage devices is defined in the proposed decomposed formulation:(i)
Yellow Squares. They are the first and the last SoC of storage devices on the planning horizon. These values are the user-defined values of SoCy,s∗ for the storage device y at the scenario s as formulated in constraint (15).(ii)
Purple Squares. They represent the scenarios that belong only to block bl. For these scenarios, the SoC variables are calculated in the correspondent subproblem bl.(iii)
Green Squares. They represent the scenarios shared by two adjacent blocks. The SoC variables are calculated in the Master Problem and formulated as fixed variables in the two correspondent subproblems for these scenarios, which guarantees the continuity of SoC in the representative period as a whole and allows to extract the Lagrange multipliers related to the SoCs variables at the first and last scenarios of each block.Figure 1
Arrangement of the scenarios innbl blocks.Figure1 presents the representative period divided into nbl blocks of scenarios. The index wbl is equivalent to the first scenario of the block Sbl, which ends in the scenario wbl+1−1 as defined in (20). Thus, wbl and wbl+1 are the frontier scenarios of block bl whose SoC levels of storage devices are defined by the master problem and imposed as fixed values for the subproblem bl. The set of all frontier scenarios Γ is defined in (21) and the set of frontier scenarios Γbl for block bl is defined in (22). The relationship between frontier scenarios and scenario indexes is expressed in (23), where nsbl is the number of scenarios in block bl and ns0 is defined as equal to 1. It is important to notice that the last frontier scenario wnbl+1 is equivalent to the scenario nsnbl+1 which is a scenario index only used to fix the SoC level of storage device y at the specified value SoCy,ns+1∗ as defined in (15) at the end of planning horizon.(20)Sbl=wbl,wbl+1,wbl+2,…,wbl+1,(21)Γ=w1,w2,…,wbl,…,wnbl,wnbl+1,(22)Γbl=wbl,wbl+1,(23)wbl=∑bl=0bl−1nsbl.


## 3.2. Master Problem

The master problem is defined in (24)–(29) and it is responsible for defining the SoC of storage devices between each block of representative scenarios and the investment in transmission lines and storage devices.(24)Cmpv=minχmp∑k∈KCCkTIkT+∑y∈YCCyYIyY+∑s∈Γαs,(25)χmp=IT,IY,SoC,α,subject to (7)-(8), considering S=Γ, (16)–(18), and:(26)SoCy,s+1−SoCy,s≤Δbl⋅py¯y,∀y∈YE,s∈Γ,(27)SoCy,s+1−SoCy,s≤Δbl⋅IyY⋅py¯y,∀y∈YC,s∈Γ,(28)Csps,κ−∑y∈Yλy,sSoCκSoCy,s−SoCy,sκ+λy,s+1SoCκSoCy,s+1−SoCy,s+1κ+…−∑y∈YCλy,sYκIyY−IyYκ−∑k∈KCλk,sTκIkT−IkTκ≤αs,∀s∈Γ,κ=1,…,v−1,(29)αs≥0.The objective function in (24) aims to minimize the investment in transmission lines and storage devices. The set of decision variables of the master problem is expressed in (25). In (26)-(27) are imposed auxiliary constraints to the master problem in order to improve the convergence of the method. These constraints limit the SoC values defined for all frontier scenarios at feasible levels that each subproblem solution can achieve. Thus, the distance between the SoC levels in each storage device to a given Γbl needs to be less to its maximum charging/discharging capacity during all block duration. The set of Benders’ cuts is formulated in (28). Finally, αs is set as a non-negative variable in (29).


## 3.3. Subproblems

The subproblems are responsible for evaluating the power system’s operational condition for a subperiod of the planning horizon. The subproblem related to the blockbl is formulated as follows:(30)Cspbl,v=minχ∑s∈SblΔbl∑g∈Gcggpgg,s+∑y∈Ycyypyy,sch+pyy,sdis+pen∑b∈Bslb,s,subject to (3)–(14), considering S=Sbl, and(31)SoCy,s=SoCy,sv,∀y∈Y,s∈Γblλy,sSoC,(32)IyY=IyYv,∀y∈YCλk,blY,(33)IkT=IkTv,∀k∈KCλk,blT,where SoCy,sv=SoCy,s∗fors=1,ns+1The objective function (30) aims to minimize the operational cost of generators by defining the dispatch of generation and use of storage devices along the subperiod defined by the block bl. The constraints (31)–(33) impose the decisions calculated by the master problem at iteration v.


## 3.4. Convergence Criteria

Two convergence criteria are evaluated in this paper as following.


### 3.4.1. Traditional Benders Decomposition Convergence Criterion

At each iterationv the algorithm computes an upper bound value of the objective function of the original problem with (34) and a lower bound value with (35). If Zupv−Zdnv/Zupv was less than a convergence criteria, e. g., 0.001, stop the iterative approach.(34)Zupv=Cmpv−∑s∈Γαsv+∑s∈SblCspbl,v,(35)Zdnv=Cmpv.where αsv is the calculated value for αs from the optimal solution of master problem at iteration v.


### 3.4.2. Proposed Convergence Criterion

Since the master problem in the proposed decomposition approach is responsible for investing and allocating the SoCs in the storage devices, a longer iterative process is needed to converge the traditional Benders decomposition convergence criterion. After defining a good expansion alternative, with no load shedding, the Benders decomposition searches for an optimal operational condition for all time windows, which can be hard to achieve. Thus, as demonstrated in the result section, it is proposed to stop the Benders decomposition when an expansion alternative without load shedding is found.The result obtained with this proposed convergence criterion is sub-optimal. However, it can be improved by performing ana posteriori simulation with the investment variables fixed at the solution values, reducing the complexity of the problem drastically since master problems became an LP problem.


## 3.4.1. Traditional Benders Decomposition Convergence Criterion

At each iterationv the algorithm computes an upper bound value of the objective function of the original problem with (34) and a lower bound value with (35). If Zupv−Zdnv/Zupv was less than a convergence criteria, e. g., 0.001, stop the iterative approach.(34)Zupv=Cmpv−∑s∈Γαsv+∑s∈SblCspbl,v,(35)Zdnv=Cmpv.where αsv is the calculated value for αs from the optimal solution of master problem at iteration v.


## 3.4.2. Proposed Convergence Criterion

Since the master problem in the proposed decomposition approach is responsible for investing and allocating the SoCs in the storage devices, a longer iterative process is needed to converge the traditional Benders decomposition convergence criterion. After defining a good expansion alternative, with no load shedding, the Benders decomposition searches for an optimal operational condition for all time windows, which can be hard to achieve. Thus, as demonstrated in the result section, it is proposed to stop the Benders decomposition when an expansion alternative without load shedding is found.The result obtained with this proposed convergence criterion is sub-optimal. However, it can be improved by performing ana posteriori simulation with the investment variables fixed at the solution values, reducing the complexity of the problem drastically since master problems became an LP problem.


## 4. Results

This section presents the results obtained for the proposed methodology. In Section4.1, it is considered the modified 6-bus Garver test system [26] to demonstrate the sensitivity of the decomposition method to variations in the number of blocks. In Section 4.2, the co-planning is evaluated in the modified 24-bus IEEE-RTS test system [27] to demonstrate the performance of the proposed methodology and to discuss the convergence criterion. In Section 4.3, the modified IEEE 118-bus test system [28] is used to demonstrate the capacity of the proposed method to solve medium-size systems and the advantages of using parallel computation.Two historical series were used to represent the hourly variability of the demand and wind. The data for the series and the modified versions of the test systems are presented in [29]. The investment cost for all transmission lines is $2 million by a mile. It was considered a subsidized cost of 16$/kW (power capacity) and 24$/KWh (energy capacity) for storage devices. As detailed in [30], the investment costs were annualized considering an interest rate of 5%, a lifetime of 60 years for the transmission lines [3], and 20 years for the storage devices [21]. It was considered an operational cost of 54.26$/MWh for non-renewable generators, and renewable ones have no operational cost.All analyses in this section consider the reduction of search space by applying the construction phase of the Greedy Randomized Adaptive Search Procedure (GRASP) heuristic method detailed in [31]. Thus, to measure the effectiveness of the proposed approach, for every branch with installed lines by the GRASP, the MILP solver and the proposed methodology consider 4, 3, and 3 candidate lines respectively for the Garver, IEEE-RTS, and IEEE-118 systems.The methodology was implemented in the MATLAB® numerical computing environment. The CPU times refer to an AMD Ryzen™ 5 2400G processor with 3.6 GHz of clock speed. MILP and LP problems were respectively solved withcplexmilp and cplexlp algorithms of CPLEX 12.9.0 (Copyright© IBM Corp.) optimization package under the opportunistic parallel optimization method with up to 4 threads. The parallelism was implemented with the asynchronous parallel programming features of the Parallel Computing Toolbox of MATLAB®.


### 4.1. 6-Bus Modified Garver Test System

This subsection presents the results obtained with the 6-bus modified Garver test system. For the Garver system, it was considered the 32nd week of the historical series, the week that the peak load of the series occurs. Thus, six simulation cases were performed considering the MILP formulation and the decomposed formulation for six different numbers of blocks. For the simulations, a tolerance of gap for the bounds of Benders decomposition was set to 0.001. The results are presented in Table2.Table 2
Simulation results for the 6-bus modified Garver test system.
Simulation caseSolution TechniqueNumber of blocksHours by blockNumber of iterationsComputational time (s)Added linesAdded storagesCost (M$)MILP-1cplexmilp———32–6, 3–5, 4–63x (2), 7x (4)13.55D-1Benders116861562–6, 3–5, 4–63x (2), 7x (4)13.55D-2Proposal35645412–6, 3–5, 4–62x (2), 8x (4)13.55D-3Proposal72448452x(2–6), 3–511x (4)13.66D-4Proposal42434452–6, 3–5, 4–62x (2), 8x (4)13.55D-5Proposal168128852–6, 3–5, 4–63x (2), 7x (4)13.55The results show that for the Garver system, a minimal test system, the complete formulation (simulation case MILP-1) performs the simulation in only 3 seconds, while the fastest case for the proposed decomposition method took 41 seconds. It was expected for a small size problem since the solver can efficiently deal with a small number of constraints and variables. For the simulation case D-5, the computational time was more significant, and the number of iterations was the smallest, which occurs since the high number of blocks grows fast the size of the master problem, reducing the efficiency of the decomposed method. Similar behavior can be noted in the simulation case D-1, the unique block insert only one Benders’ cut by iteration, demanding more iterations to converge the problem with causes more computational time to solve the problem. Thus, the better way is to choose a given number of blocks that balance between the size of subproblems and the size of the master problem. This aspect will be discussed in the subsequent section.


### 4.2. 24-Bus Modified IEEE-RTS Test System

For the IEEE-RTS system, it was considered the weeks 30 to 33 of the historical series, totaling a representative period of 762 hours. In this section, three simulation cases are performed, and the results are presented in Table3. The simulation case D-6 considers a tolerance of 0.001 for the gap between the bounds of Benders’ decomposition, while case D-7 modifies the stop criterion of Benders’ decomposition to return the first solution without load shedding. The cases D-6 and D-7 consider seven blocks of 96 hours each. In Table 3, the number of iterations and computational time for simulation case D-7 regards the values spent at the search of the first expansion alternative without load shedding, followed by the values spent at the “a posteriori” simulation to optimize the operational cost as detailed in Section 3.4.Table 3
Simulation results for 24-bus modified IEEE-RTS test system.
Simulation caseSolution techniqueNumber of iterationsComputational time (s)Added linesAdded storagesOpe Cost (M$)Inv Cost (M$)MILP-2cplexmilp—1762x (7–8)1x (5), 2x (6), 2x (14)185.238.838D-6Proposal33211142x (7–8)1x (5), 2x (6), 2x (14)185.308.838D-7Proposal97 + 6294 + 152x (7–8)1x (5), 2x (6), 1x (8), 1x (14)185.308.838For simulation case D-7, considering the proposed stop criterion, the decomposition method achieved a similar result with 26% of the total computational time compared to simulation D-6. It can be seen that the “a posteriori” operational problem took only 15 seconds and added six iterations of problems. Thea posteriori simulation reduced the operational cost from 185.59M$ to 185.30M$. Those results show that the modified stop criterion can be used to obtain sub-optimal solutions with a shorter simulation time. However, even for the 24-bus IEEE-RTS considering four weeks of the historical series, the complete formulation, simulation case MILP-2, showed to be a better option since this simulation was 6.3 faster than simulation case D-6 and 1.7 faster than simulation case D-7.


### 4.3. 118-Bus Modified IEEE-118 Test System

This section discusses the results of the proposed methodology with a medium-size test system, the 118-bus IEEE-118. Thus, six simulation cases were performed:(i)
Cases MILP-3 and D-8 consider the same four weeks used in Section 4.2.(ii)
Cases MILP-4 and D-9 increase the problem size by doubling the representative period considering from week 27 to 34.(iii)
For simulation cases MILP-5 and D-10, it was considered 52 weeks in hourly resolution, i.e., a time window of 8736 hours. The representative period in D-10 was divided into 26 blocks of 336 hours each.D-8 and D-9 consider, respectively, 7 and 14 blocks of 96 hours and the modified stop criterion described in Section4.2. For simulation cases D-8, D-9, and D-10, the number of iterations regards the number of iterations of the simulation case plus the number of iterations of the a posteriori operational problem. Also, the computational times are referent for both simulations as discussed in Section 3.4.The results are presented in Table4. It can be seen that for larger systems, the proposed decomposition method reduces the computational time. For simulation cases considering four weeks, D-8 was 1.6 times faster and obtained the same solution as MILP-3. By doubling the number of weeks, MILP-4 increased the computational time by 3.9 times (4.6 hours) in comparison to MILP-3, while D-9 increased only 1.5 times (25.2 minutes) in comparison to D-8. However, the D-9 achieved a sub-optimal solution, 0.2% more expensive than MILP-4. As expected, it may occur by using the modified stop criterion.Table 4
Simulation results for the 118-bus modified IEEE-118 test system.
Simulation caseSolution techniqueNumber of iterationsComputational time (h)Added linesAdded storagesOpe. cost (M$)Inv. cost (M$)MILP-3cplexmilp—1.4416–17, 19–342x (3), 1x (4), 1x (6)273.7428.60D-8Proposal332 + 80.88 + 0.0216–17, 19–342x (4), 2x (6)273,8028.60MILP-4cplexmilp—5.6016–17, 19–342x (3), 1x (4), 1x (6)531.2128.60D-9Proposal221 + 61.29 + 0.038–5, 19–341x (3), 2x (6)531.2229.67MILP-5cplexmilp——————D-10Proposal33 + 72.14 + 0.348–5, 19–341x (3), 2x (6)1,994.0735.57Regarding the simulation cases MILP-5 and D-10, it can be observed that the computational time for solving the co-planning problem (D-10) was only 1.88 times greater than the simulation case D-9. It must be emphasized that simulation case D-10 has a time window 6.5 times greater than D-9. Moreover, the whole MILP problem cannot be solved using the CPLEX solver in the personal computer used in all tests. In other words, the increase in system size and complexity can still be achieved by using the proposed methodology.The computational times presented for D-8, D-9 and D-10 consider the parallel computing of the subproblems, an advantage of considering the decomposition approach. Parallel computing strongly depends on the machine that runs the code, but it is easy to configure the nodes of computation by running a few iterations and measuring the performance obtained for different numbers of computation cores. The machine used for the tests has 4 computation cores and 8 threads, implying that up to 8 subproblems could be solved simultaneously. The performance of CPLEX solvers is improved by using the default opportunistic parallel mode,which was adjusted to up to 4 threads forcplexlp solver, the D-8 and D-9, was set to be solved with 2 parallel cores of processing, and the D-10 with 3 cores. In order to exemplify, the computation times to solve all subproblems of simulation cases D-9, D-9, and D-10 for the 5 first iterations are presented in Table 5.Table 5
Computational time (in seconds) to solve subproblems for simulation cases D-8, D-9 and D-10 by varying the number of computational cores of parallel computing.
No. of coresCase1234D-877.455.448.548.9D-9138.097.387.885.1D-102,376.81,211.71,035.6998.1The memory usage for solving the simulation cases of IEEE-118 is presented in Table6. For the simulation cases considering the proposed decomposition method, Table 6 presents the memory usage of master problems at the first iteration. It can be seen that the proposed methodology can reduce the memory usage in comparison to solving the problem at once, as expected. As shown in Table 6, the MILP-5 simulation case is formulated by a MILP problem with more than 5.5 million variables, even considering the simplified formulation of the co-planning presented in this study. On the other hand, simulation D-10 (numerically equivalent to MILP-5) has a relatively small master problem and a set of subproblems with 103,852 variables.Table 6
Memory usage (in Mb) for MILP, master problem (MP) and one subproblem (SP) and the number of integer variables (NI) and continuous variables for MILP (NC-MILP), master problem (NC-MP) and one subproblem (NC-SP).
Simulation caseMemory usageNo. of variablesMILPMPSPNINC-MILPNC-MPNC-SPMILP-365,48——20426,052——D-8—0.069.3020—3960,888MILP-4130.91——20852,100——D-9—0.079.3020—7460,888MILP-5850.55——205,538,628——D-10—0.0932.3820—134103,852D-10∗—0.05840.0020—95,538,648An additional simulation case D-10∗ is presented in Table 6, which is the same case D-10 but considering only one block covering the 52 weeks. It can be seen that the subproblem without the proposed methodology contains a similar number of variables to the equivalent MILP problem disregarding the integer variables. Besides removing the integer variables reduces the problem’s complexity, it continues to be a considerable size mathematical problem.


## 4.1. 6-Bus Modified Garver Test System

This subsection presents the results obtained with the 6-bus modified Garver test system. For the Garver system, it was considered the 32nd week of the historical series, the week that the peak load of the series occurs. Thus, six simulation cases were performed considering the MILP formulation and the decomposed formulation for six different numbers of blocks. For the simulations, a tolerance of gap for the bounds of Benders decomposition was set to 0.001. The results are presented in Table2.Table 2
Simulation results for the 6-bus modified Garver test system.
Simulation caseSolution TechniqueNumber of blocksHours by blockNumber of iterationsComputational time (s)Added linesAdded storagesCost (M$)MILP-1cplexmilp———32–6, 3–5, 4–63x (2), 7x (4)13.55D-1Benders116861562–6, 3–5, 4–63x (2), 7x (4)13.55D-2Proposal35645412–6, 3–5, 4–62x (2), 8x (4)13.55D-3Proposal72448452x(2–6), 3–511x (4)13.66D-4Proposal42434452–6, 3–5, 4–62x (2), 8x (4)13.55D-5Proposal168128852–6, 3–5, 4–63x (2), 7x (4)13.55The results show that for the Garver system, a minimal test system, the complete formulation (simulation case MILP-1) performs the simulation in only 3 seconds, while the fastest case for the proposed decomposition method took 41 seconds. It was expected for a small size problem since the solver can efficiently deal with a small number of constraints and variables. For the simulation case D-5, the computational time was more significant, and the number of iterations was the smallest, which occurs since the high number of blocks grows fast the size of the master problem, reducing the efficiency of the decomposed method. Similar behavior can be noted in the simulation case D-1, the unique block insert only one Benders’ cut by iteration, demanding more iterations to converge the problem with causes more computational time to solve the problem. Thus, the better way is to choose a given number of blocks that balance between the size of subproblems and the size of the master problem. This aspect will be discussed in the subsequent section.


## 4.2. 24-Bus Modified IEEE-RTS Test System

For the IEEE-RTS system, it was considered the weeks 30 to 33 of the historical series, totaling a representative period of 762 hours. In this section, three simulation cases are performed, and the results are presented in Table3. The simulation case D-6 considers a tolerance of 0.001 for the gap between the bounds of Benders’ decomposition, while case D-7 modifies the stop criterion of Benders’ decomposition to return the first solution without load shedding. The cases D-6 and D-7 consider seven blocks of 96 hours each. In Table 3, the number of iterations and computational time for simulation case D-7 regards the values spent at the search of the first expansion alternative without load shedding, followed by the values spent at the “a posteriori” simulation to optimize the operational cost as detailed in Section 3.4.Table 3
Simulation results for 24-bus modified IEEE-RTS test system.
Simulation caseSolution techniqueNumber of iterationsComputational time (s)Added linesAdded storagesOpe Cost (M$)Inv Cost (M$)MILP-2cplexmilp—1762x (7–8)1x (5), 2x (6), 2x (14)185.238.838D-6Proposal33211142x (7–8)1x (5), 2x (6), 2x (14)185.308.838D-7Proposal97 + 6294 + 152x (7–8)1x (5), 2x (6), 1x (8), 1x (14)185.308.838For simulation case D-7, considering the proposed stop criterion, the decomposition method achieved a similar result with 26% of the total computational time compared to simulation D-6. It can be seen that the “a posteriori” operational problem took only 15 seconds and added six iterations of problems. Thea posteriori simulation reduced the operational cost from 185.59M$ to 185.30M$. Those results show that the modified stop criterion can be used to obtain sub-optimal solutions with a shorter simulation time. However, even for the 24-bus IEEE-RTS considering four weeks of the historical series, the complete formulation, simulation case MILP-2, showed to be a better option since this simulation was 6.3 faster than simulation case D-6 and 1.7 faster than simulation case D-7.


## 4.3. 118-Bus Modified IEEE-118 Test System

This section discusses the results of the proposed methodology with a medium-size test system, the 118-bus IEEE-118. Thus, six simulation cases were performed:(i)
Cases MILP-3 and D-8 consider the same four weeks used in Section 4.2.(ii)
Cases MILP-4 and D-9 increase the problem size by doubling the representative period considering from week 27 to 34.(iii)
For simulation cases MILP-5 and D-10, it was considered 52 weeks in hourly resolution, i.e., a time window of 8736 hours. The representative period in D-10 was divided into 26 blocks of 336 hours each.D-8 and D-9 consider, respectively, 7 and 14 blocks of 96 hours and the modified stop criterion described in Section4.2. For simulation cases D-8, D-9, and D-10, the number of iterations regards the number of iterations of the simulation case plus the number of iterations of the a posteriori operational problem. Also, the computational times are referent for both simulations as discussed in Section 3.4.The results are presented in Table4. It can be seen that for larger systems, the proposed decomposition method reduces the computational time. For simulation cases considering four weeks, D-8 was 1.6 times faster and obtained the same solution as MILP-3. By doubling the number of weeks, MILP-4 increased the computational time by 3.9 times (4.6 hours) in comparison to MILP-3, while D-9 increased only 1.5 times (25.2 minutes) in comparison to D-8. However, the D-9 achieved a sub-optimal solution, 0.2% more expensive than MILP-4. As expected, it may occur by using the modified stop criterion.Table 4
Simulation results for the 118-bus modified IEEE-118 test system.
Simulation caseSolution techniqueNumber of iterationsComputational time (h)Added linesAdded storagesOpe. cost (M$)Inv. cost (M$)MILP-3cplexmilp—1.4416–17, 19–342x (3), 1x (4), 1x (6)273.7428.60D-8Proposal332 + 80.88 + 0.0216–17, 19–342x (4), 2x (6)273,8028.60MILP-4cplexmilp—5.6016–17, 19–342x (3), 1x (4), 1x (6)531.2128.60D-9Proposal221 + 61.29 + 0.038–5, 19–341x (3), 2x (6)531.2229.67MILP-5cplexmilp——————D-10Proposal33 + 72.14 + 0.348–5, 19–341x (3), 2x (6)1,994.0735.57Regarding the simulation cases MILP-5 and D-10, it can be observed that the computational time for solving the co-planning problem (D-10) was only 1.88 times greater than the simulation case D-9. It must be emphasized that simulation case D-10 has a time window 6.5 times greater than D-9. Moreover, the whole MILP problem cannot be solved using the CPLEX solver in the personal computer used in all tests. In other words, the increase in system size and complexity can still be achieved by using the proposed methodology.The computational times presented for D-8, D-9 and D-10 consider the parallel computing of the subproblems, an advantage of considering the decomposition approach. Parallel computing strongly depends on the machine that runs the code, but it is easy to configure the nodes of computation by running a few iterations and measuring the performance obtained for different numbers of computation cores. The machine used for the tests has 4 computation cores and 8 threads, implying that up to 8 subproblems could be solved simultaneously. The performance of CPLEX solvers is improved by using the default opportunistic parallel mode,which was adjusted to up to 4 threads forcplexlp solver, the D-8 and D-9, was set to be solved with 2 parallel cores of processing, and the D-10 with 3 cores. In order to exemplify, the computation times to solve all subproblems of simulation cases D-9, D-9, and D-10 for the 5 first iterations are presented in Table 5.Table 5
Computational time (in seconds) to solve subproblems for simulation cases D-8, D-9 and D-10 by varying the number of computational cores of parallel computing.
No. of coresCase1234D-877.455.448.548.9D-9138.097.387.885.1D-102,376.81,211.71,035.6998.1The memory usage for solving the simulation cases of IEEE-118 is presented in Table6. For the simulation cases considering the proposed decomposition method, Table 6 presents the memory usage of master problems at the first iteration. It can be seen that the proposed methodology can reduce the memory usage in comparison to solving the problem at once, as expected. As shown in Table 6, the MILP-5 simulation case is formulated by a MILP problem with more than 5.5 million variables, even considering the simplified formulation of the co-planning presented in this study. On the other hand, simulation D-10 (numerically equivalent to MILP-5) has a relatively small master problem and a set of subproblems with 103,852 variables.Table 6
Memory usage (in Mb) for MILP, master problem (MP) and one subproblem (SP) and the number of integer variables (NI) and continuous variables for MILP (NC-MILP), master problem (NC-MP) and one subproblem (NC-SP).
Simulation caseMemory usageNo. of variablesMILPMPSPNINC-MILPNC-MPNC-SPMILP-365,48——20426,052——D-8—0.069.3020—3960,888MILP-4130.91——20852,100——D-9—0.079.3020—7460,888MILP-5850.55——205,538,628——D-10—0.0932.3820—134103,852D-10∗—0.05840.0020—95,538,648An additional simulation case D-10∗ is presented in Table 6, which is the same case D-10 but considering only one block covering the 52 weeks. It can be seen that the subproblem without the proposed methodology contains a similar number of variables to the equivalent MILP problem disregarding the integer variables. Besides removing the integer variables reduces the problem’s complexity, it continues to be a considerable size mathematical problem.


## 5. Conclusions

This study presented a novel formulation to solve the co-planning in transmission and storage devices with the multicut Benders decomposition dividing the operational problem into several blocks. The proposal showed to reduce the memory usage and the computational time to solve co-planning problems considering several weeks of operation.A convergence criterion was proposed to find sub-optimal expansion alternatives with a relatively short simulation time. It has been shown that the block-based multicut Benders decomposition can be faster with the use of parallel computation. Using only 8 processing units, the personal computer could solve the problem in 60% of the time spent in a sequential simulation.For future works, it is proposed to evaluate the performance of the block-based multicut Benders decomposition in more complex models with dynamic constraints considering storage devices, generator ramping constraints, hydrothermal systems operation scheduling, and pumped storage hydropower.



---

*Source: 6289475-2022-10-07.xml*