(19a) MILP Formulation and Nested Decomposition Algorithm for Electric PowerInfrastructure Planning

Energy systems planning models allow the evaluation of alternate scenarios for future growth, providing information to support the decision-making process and the selection of technologies in the power sector. Generation and transmission expansion models can vary widely in scope (local versus regional) as well as in resolution of time and space. These models can be used to study the impact of new technology developments, resource cost trends, and policy shifts on the projected generation mix in order to meet future demand. The increasing contribution of intermittent renewable generation to the power grid poses new challenges that are not fully covered by the traditional power systems planning models, such as the multi-scale integration of detailed operating decisions in the hourly (or sub-hourly) level with investment decisions over a few decades.

In this paper, we address the long-term planning of electric power infrastructures considering high renewable penetration. To capture the intermittency of those sources, we propose a deterministic MILP planning model that includes operating decisions on an hourly basis. This model optimizes the generation expansion required to meet the projected electricity demand over the next few decades while taking into account detailed operational constraints (i.e., unit commitment), the variability and intermittency of renewable generation sources, and the power flow between regions. The modeling framework takes the viewpoint of a central planning entity whose goal is to identify the energy source (nuclear, coal, natural gas, wind and solar), generation technology (e.g., steam, combustion and wind turbines, photovoltaic and concentrated solar panels), location (regions), and generation capacity that can meet the projected electricity demand, while minimizing the amortized capital investment of all new generating units, the retrofit cost of old units that reached their expected lifetime, the operation and maintenance costs of both new and existing units, and potential environmental costs (e.g. carbon tax and renewable generation quota).

The major challenge lies in the multi-scale integration of detailed operating decisions at the hourly level with investment planning decisions over a few decades, which directly impacts its computational burden. Therefore, we adopt judicious approximations and aggregations, such as time sampling [1, 2] and generator clustering [3] to reduce the size of the model. Although there is novelty in the formulation of the problem, the main contribution of this work is in the solution strategy. We propose a decomposition algorithm based on Nested Benders Decomposition [4] for mixed-integer multi-period problems. This framework was originally developed for stochastic programming [5, 6] but we have adapted it to deterministic multi-period problems, and extended it to handle integer and continuous state variables. We introduce three valid cuts to be used in this decomposition, and propose acceleration techniques to improve the overall performance of the algorithm [7]. This algorithm targets large-scale multi-period problems and allows us to evaluate the impact of the number of representative days per year in the planning strategy over a long time horizon.

The proposed formulation and algorithm are applied to a case study in the region managed by the Electric Reliability Council of Texas (ERCOT) for a 30 year planning horizon. We first solve the proposed model for 1 to 12 representative days per year to assess the impact of the number of day samplings in the planning strategy. We show that for the proposed model and case study, it is sufficient to have 4 representative days per year in order to adequately represent the variability in load and capacity factor for the different regions. Furthermore, we solve our model as a full-space MILP, as well as using the Nested Decomposition with the proposed cuts for the 4 representative days variant of the model, and applied the acceleration technique to the cut with the best performance. The two best versions of the algorithm are also tested for the 12 representative day. For both the 4-days and 12-days representations, we demonstrate massive computational savings with our decomposition.

References

[1] A. Pina, C. Silva, and P. Ferrão, (2011). Modeling hourly electricity dynamics for policy making in long-term scenarios, Energy Policy, vol. 39, no. 9, pp. 4692 - 4702.

[2] P. Nahmmacher, E. Schmid, L. Hirth, and B. Knopf (2016), Carpe diem: A novel approach to select representative days for long-term power system modeling, Energy, vol. 112, pp. 430 - 442.

[3] Palmintier, B. S., & Webster, M. D. (2014). Heterogeneous Unit Clustering for Efficient Operational Flexibility Modeling. IEEE Trans. Power Syst. IEEE Transactions on Power Systems, 29, 1089-1098.

[4] Zou, J., Ahmed, S., & Sun, X. A. (2016). Stochastic Dual Dynamic Integer Programming, Submitted for publication, url: http://www.optimization-online.org/DB_FILE/2016/05/5436.pdf

[5] J. R. Birge, (1985). Decomposition and partitioning methods for multistage stochastic linear programs, Operations Research, vol. 33, no. 5, pp. 989-1007.

[6] M. V. F. Pereira and L. M. V. G. Pinto, (1991). Multi-stage stochastic optimization applied to energy planning, Mathematical Programming, vol. 52, no. 1, pp. 359-375.

[7] Lara, C. L., Mallapragada, D., Papageorgiou, D., Venkatesh, D., & Grossmann, I.E. (2017) MILP Formulation and Nested Decomposition Algorithm for Electric Power Infrastructure Planning, Submitted for publication.