NEP is one of the main strategic decisions in power systems and has a deep, long-lasting impact on the operations of the system. Relatively recent developments in power systems, such as renewable integration or regional planning, have increased the complexity and relevance of this problem considerably. Market integration is the current paradigm to achieve a competitive, sustainable and reliable electric system and the network is a facilitator in this process. This is particularly true in the case of the EU. The design of large-scale network expansions poses considerable challenges that have been addressed in a vast array of both projects and academic literature. Existing thorough academic reviews on this topic can be found in references [11, 12, 13]. These works are a very good starting point to understand the state of the art of the network expansion planning challenges and current approaches.

Among the current challenges to be addressed for the network expansion planning we can mention the following ones:

- Its coordination with GEP, as discussed previously. On the one hand, GEP is a deregulated business activity while NEP is mostly regulated. On the other hand, generation investments can take around three years, while network expansion need to be anticipated longer periods.
- Renewable integration is one of the major drivers for investing in new transmission lines. Onshore and offshore wind power, and solar generation are renewable technologies currently being developed at large scale to meet the low-carbon electricity generation targets. A large part of this generation is located in remote areas far from the load centers requiring transmission reinforcements or new connections. Besides, the intermittent nature of these renewables introduces operational challenges and, from the network planning point of view, many varied operation situations should be considered.
- Market integration is the current paradigm to achieve a competitive, sustainable and reliable electric system and the network is a facilitator in this process. The creation of an European internal market with strong enough interconnection capacity among the member states increases the scope of the planning process, from a national activity to a European scale.

Different mathematical optimization techniques are used for solving the network expansion planning. They can be classified as: classical and non-classical (metaheuristic) methods see references [12, 13].

- Classical methods include linear, nonlinear and mixed integer programming methods. Linear optimization ignores the discrete nature of the investment decisions but still it can be useful is system is too large to be solved with discrete variables or a relaxed solution is good enough. A transportation or a direct-current (DC) load flow fit in this linear formulation. Nonlinear, in particular quadratic, models appear as a way to represent transmission losses. Finally, mixed integer optimization allows considering the integer nature of the decisions. If stochasticity in some parameters is included then models become stochastic and, therefore, decomposition techniques should be used for large-scale systems. Among them, Benders decomposition, Lagrangean relaxation or column generation are frequently used see also the references listed in the section DNEP.
- Non-classical metaheuristic methods include Greedy Randomized Adaptive Search Procedure (GRASP), tabu search, genetic algorithms, simulated annealing, swarm intelligence, ant colony optimization, differential evolution, ordinal optimization, etc.

Network expansion planning is per se a multicriteria decision problem although frequently a single objective function is used by combining and monetizing the multiple criteria under a single one with the weighted-sum method. The main criteria are usually: costs, environmental impact, market integration and other exogenous factors. Costs are measured by the attributes such as investment and operation costs of the transmission decisions but also operation costs of the system. In the cost criterion, it can also be introduced the reliability impact. Environmental impact is determined by attributes as amount of renewable integration or curtailment avoided at system level and impact of the line construction. Market integration is accounted as number of hours of market splitting. Social acceptance is an exogenous criterion and, nowadays, is a major concern of the current planning process and being the cause of many delays.

A wide variety of models and the corresponding mathematical optimization techniques are used in solving the network expansion planning. Initially, models can be classified as either linear, non-linear, mixed integer linear (MILP), or non-linear (MINLP). Linear models, often based on transportation or direct-current (DC) load-flow, ignore the discrete nature of the investment decisions, but can be useful as an approximation. Nonlinear models, often quadratic, represent transmission losses, but still usually ignore the discrete nature of the investment decisions. MILP approaches allow for the integer nature of the investment decisions to be considered, but are restricted to an approximation of the non-linearity, either using piece-wise linearisations, or linearisations including the DC and transportation load-flow. If stochasticity in some of the parameters is considered, then models may become stochastic challenging to solve already, and decomposition techniques are often used for large-scale instances. Finally, one may consider the the full MINLP model: there, both the discrete and non-linear features of the problem are modelled faithfully, but the problem is challenging.

Further, one may consider a wide variety of objectives, although a single objective function is often obtaiend by combining the multiple criteria into one, e.g., by considering the monetary costs associated with each criterion, and minimising the total monetary costs across all criteria. The main criteria are usually: investment costs, costs of operations (OPEX), reliability issues, environmental impact, market integration factors, and rarely, other factors. While investment costs are often relatively straightforward to estimate, the operational expenses associated may be harder to estimate, especially considering the long planning horizon often considered. Similarly, the impact on reliability is often modelleded only very approximately. Environmental impact is often evaluated in terms of the amounts of renewable integration made possible, or curtailment avoided at system level, in response to the line construction. Market integration is accounted as number of hours of market splitting. When the monetary costs of such approaches cannot be approximated, metaheuristic approaches may provide a sample of the feasible solutions, without any guarantees of their distance to optimality.

Considerig GEP is a deregulated business activity, while NEP is mostly regulated at both national and super-national levels, one may also introduce market considerations explicitly. For example, one may consider an equilibrium in a pool-based market at one level, possibly including spot prices, and the transmission and generation expansion at another level. Such bi-level and multi-level models have been attempted, but often increase the complexity to a point, where real-life applicability is limited, considering the extent of many markets. In particular: Many super-national markets area already in operations. The eventual creation of an European internal market with strong-enough interconnection capacity among the member states, for instance, increases the scope and complexity of the planning process.

Further, one may attempt to solve a problem combining the expansion of transmission (NEP) with the expansion of generation (GEP). Clearly, generation expansion hence clearly has bearing upon network expansion, and vice versa. In particular, renewable integration is one of the major drivers for investing in new transmission lines. Onshore and offshore wind power, and solar generation are renewable technologies currently being developed at large scale to meet the low-carbon electricity generation targets. A large part of this generation is located in remote areas far from the load centres, and hence requires transmission reinforcements or new connections. Besides, the intermittent nature of these renewables introduces operational challenges and, from the network planning point of view, many varied operation situations should be considered. In such integrated problems, the size of the instances grows. See an independent entry.

Within linear models, such as transportation or direct-current (DC) load-flow, general-purpose linear programming optimisation software is often used, based either on simplex or interior-point (barrier) methods. Often, it turns out to be challenging to devise a problem-specific method, whose performance improves upon the general-purpose methods. Still, in case of particularly large-scale instances, problem-specific decompositions such as column generation are used.

Within nonlinear models, often quadratic, a wide variety of methods is used, considering the limitations of the general-purpose non-linear programming optimisation software. Since 1990, interior-point method have been most popular. First-order methods, including gradient and coordinate descent, and their stochastic variants, had been used prior to this and also very recently, inspired by their resurgence within machine learning.

Within MILP models, there has been much recent progress in general-purpose optimisation software based on branch-and-bound-and-cut. Often, modest instances considering either piece-wise linearisations or uncertainty, can be solved exactly using the general-purpose software. Decompositions, such as Benders decomposition, Lagrangian relaxation or column generation are frequently used.

Within MINLP models, the methods are an active area of research, considering the limitations of the general-purpose non-linear programming optimisation software. [8] surveys three convergent approaches, based on piece-wise linearisation of certain higher-dimensional surfaces, based on the method of moments, and based on combining lifting and branching. The preliminary conclusion is that the combining lifting and branching may be the most promising.

We refer to [2,3,4,7,11,12,13] for detailed surveys. See [14] for an illustration of the impact of security of transmission constraints, [8] for an example of the impact of the choice of model (AC vs. PWL vs. DC), [17] for an example of the impact of the uncertainty. Within multi-stage approaches, there are very well-developed decompositions [1], and for a pro-active Transmission Expansion Planning model by considering related Gencos generation capacity expansion planning.

Within two-stage approaches, there is a long tradition of work on decomposition methods [2,9], although even a monolithic scenario expansion may be tractable [6,15,6], when AC and security of transmission constraints are ignored and the model of the network [15] is sufficiently coarse. The incorporation of market considerations [10,11] complicates matters considerably.

[1] S. Ahmed, A. King, G. Parija, "A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty," Journal of Global Optimization, Vol. 26, pp. 3–24, 2003.

[2] L. Baringo and A. J. Conejo, “Transmission and Wind Power Investment,” IEEE Transactions on Power Systems, Vol. 27 (2): 885-893, 2012

[2] R. Hemmati, R. Hooshmand, A. Khodabakhshian, "Comprehensive review of generation and transmission expansion planning", IET Generation Transmission Distribution 7(2013) 955–964.

[3] S. R. Khuntia, B. W. Tuinema, J. L. Rueda, and M. A. M. M. van der Meijden, “Time-horizons in the planning and operation of transmission networks: an overview”, IET Generation Transmission Distribution, Vol. 10 (4): 841–848, 2016.

[4] G. Latorre, R. D. Cruz, J. M. Areiza, and A. Villegas, "Classification of publications and models on transmission expansion planning," IEEE Transactions on Power Systems, vol. 18, pp. 938-946, 2003.

[5] W. Li and R. Billinton, “A minimum cost assessment method for composite generation and transmission system expansion planning,” IEEE Transactions on Power Systems, Vol. 8(2): 628–635, 1993

[6] J. A. López, K. Ponnambalam, and V. H. Quintana, “Generation and transmission expansion under risk using stochastic programming,” IEEE Transactions on Power Systems, Vol. 22(3), 1369–1378, Aug. 2007

[7] S. Lumbreras, A. Ramos "The new challenges to transmission expansion planning. Survey of recent practice and literature review," Electric Power Systems Research 134: 19-29, May 2016 10.1016/j.epsr.2015.10.013

[8] J. Marecek, M. Mevissen, and J. C. Villumsen, “MINLP in transmission expansion planning,” 2016 Power Systems Computation Conference (PSCC), 1-8, June 2016

[9] M. Pereira, L. Pinto, S. Cunha, and G. Oliveira, “A decomposition approach to automated generation/transmission expansion planning,” IEEE Transactions on Power Apparatus and Systems, Vol. 104(11), 3074–3083, 1985

[10] D. Pozo, E. Sauma, J. Contreras, “A Three-Level Static MILP Model for Generation and Transmission Expansion Planning,“ IEEE Transactions on Power Systems, 10.1109/TPWRS.2012.2204073, 2013.

[11] J. H. Roh, M. Shahidehpour, and Y. Fu, “Market-based coordination of transmission and generation capacity planning,” IEEE Transactions on Power Systems, Vol. 22(4), 1406–1419, Nov. 2007

[12] M. Shahidehpour, “Investing in expansion: The many issues that cloud electricity planning,” IEEE Power and Energy Magazine, 14-18, Jan 2004

[13] M. Shahidehpour, “Global broadcast — transmission planning in restructured systems,” IEEE Power and Energy Magazine., Vol. 5(5), 18-20, Sep./Oct. 2007

[14] M. Shahidehpour, W. Tinney, and Y. Fu, “Impact of security on power system operation,” IEEE Proceedings, Vol. 93(11), 2013 – 2025, Nov. 2005

[15] Y. Scholz, Renewable Energy Based Electricity Supply At Low Costs – Development Of The Remix Model And Application For Europe, PhD Dissertation, German Aerospace Center (DLR), Institute of Technical Thermodynamics, 2012

[16] J. A. Taylor, F. S. Hover, “Linear Relaxations for Transmission System Planning,“ IEEE Transactions on Power Systems, Vol. 26(4): 2533–2538, 2011

[17] A. H. van der Weijde and B. F. Hobbs, “The economics of planning electricity transmission to accommodate renewables: Using two-stage optimisation to evaluate flexibility and the cost of disregarding uncertainty,” Energy Economics, Vol. 34(5), 2089-2101, Sept. 2012

Dr Jakub Marecek, IBM

Prof. Laureano Escudero, Universidad Rey Juan Carlos

Dr Fabrizio Lacalandra, QuanTek