NEP is one of the main strategic decisions in power systems and has a de=
ep, long-lasting impact on the operations of the system. Relatively recent =
developments in power systems, such as renewable integration or regional pl=
anning, have increased the complexity and relevance of this problem conside=
rably. 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.

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

- Its coordination with GEP, as discussed previously. On the one ha= nd, GEP is a deregulated business activity while NEP is mostly regulated. O= n 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 i= n new transmission lines. Onshore and offshore wind power, and solar genera= tion are renewable technologies currently being developed at large scale to= meet the low-carbon electricity generation targets. A large part of this g= eneration is located in remote areas far from the load centers requiring tr= ansmission reinforcements or new connections. Besides, the intermittent nat= ure of these renewables introduces operational challenges and, from the net= work planning point of view, many varied operation situations should be con= sidered.
- Market integration is the current paradigm to achieve a competiti= ve, sustainable and reliable electric system and the network is a facilitat= or in this process. The creation of an European internal market with strong= enough interconnection capacity among the member states increases the scop= e of the planning process, from a national activity to a European scale.

Different mathematical optimization techniques are used for solvin= g 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 pro=
gramming methods. Linear optimization ignores the discrete nature of the in=
vestment 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 tran=
sportation or a direct-current (DC) load flow fit in this linear formulatio=
n. Nonlinear, in particular quadratic, models appear as a way =
to represent transmission losses. Finally, mixed integer optimization allow=
s considering the integer nature of the decisions. If stochasticity in some=
parameters is included then models become stochastic and, therefore, decom=
position techniques should be used for large-scale systems. Among them, Ben=
ders decomposition, Lagrangean relaxation or column generation are frequent=
ly used see also the references listed in the section DNEP.
- Non-classical metaheuristic methods include Greedy Randomized Ada=
ptive Search Procedure (GRASP), tabu search, genetic algorithms, simulated =
annealing, swarm intelligence, ant colony optimization, differential evolut=
ion, ordinal optimization, etc.

Network expansion planning is per se a multicriteria decision prob= lem although frequently a single objective function is used by combining an= d 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 attribu= tes such as investment and operation costs of the transmission decisions bu= t also operation costs of the system. In the cost criterion, it can also be= introduced the reliability impact. Environmental impact is determined by a= ttributes as amount of renewable integration or curtailment avoided at syst= em level and impact of the line construction. Market integration is account= ed as number of hours of market splitting. Social acceptance is an ex= ogenous criterion and, nowadays, is a major concern of the current p= lanning 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 transportatio= n or direct-current (DC) load-flow, ignore the discrete nature of the inves= tment decisions, but can be useful as an approximation. Nonlinear models, o= ften 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 restr= icted to an approximation of the non-linearity, either using piece-wise lin= earisations, or linearisations including the DC and transportation load-flo= w. If stochasticity in some of the parameters is considered, then models ma= y become stochastic challenging to solve already, and decomposition techniq= ues 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 singl= e objective function is often obtaiend by combining the multiple criteria i= nto one, e.g., by considering the monetary costs associated with each crite= rion, and minimising the total monetary costs across all criteria. The main= criteria are usually: investment costs, costs of operations (OPEX), reliab= ility 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. Simila= rly, the impact on reliability is often modelleded only very approximately.= Environmental impact is often evaluated in terms of the amounts of renewab= le integration made possible, or curtailment avoided at system level, in re= sponse to the line construction. Market integration is accounted as number = of hours of market splitting. When the monetary costs of such approaches ca= nnot 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 r= egulated at both national and super-national levels, one may also introduce= market considerations explicitly. For example, one may consider an equilib= rium in a pool-based market at one level, possibly including spot prices, a= nd the transmission and generation expansion at another level. Such bi-leve= l and multi-level models have been attempted, but often increase the comple= xity to a point, where real-life applicability is limited, considering the = extent of many markets. In particular: Many super-national markets area alr= eady in operations. The eventual creation of an European internal mar= ket with strong-enough interconnection capacity among the member states, fo= r instance, increases the scope and complexity of the planning process.

Further, one may attempt to solve a problem combining the expansion of t= ransmission (NEP) with the expansion of generation (GEP). Clearly, generati= on expansion hence clearly has bearing upon network expansion, and vice ver= sa. In particular, renewable integration is one of the major drivers for in= vesting in new transmission lines. Onshore and offshore wind power, and sol= ar 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, an= d hence requires transmission reinforcements or new connections. Besides, t= he intermittent nature of these renewables introduces operational challenge= s and, from the network planning point of view, many varied operation situa= tions should be considered. In such integrated problems, the size of the in= stances 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 us= ed, based either on simplex or interior-point (barrier) methods. Often, it = turns out to be challenging to devise a problem-specific method, whose perf= ormance improves upon the general-purpose methods. Still, in case of partic= ularly large-scale instances, problem-specific decompositions such as colum= n generation are used.

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

Within MILP models, there has been much recent progress in general-purpo= se optimisation software based on branch-and-bound-and-cut. Often, modest i= nstances 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 a= re frequently used.

Within MINLP models, the methods are an active area of research, conside= ring the limitations of the general-purpose non-linear programming optimisa= tion 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 c= onclusion is that the combining lifting and branching may be the most promi= sing.

We refer to [2,3,4,7,11,12,13] for detailed surveys. See [14] for an ill= ustration 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 Tr= ansmission Expansion Planning model by considering related Gencos generatio= n capacity expansion planning.

Within two-stage approaches, there is a long tradition of work on decomp= osition methods [2,9], although even a monolithic scenario expansion may be= tractable [6,15,6], when AC and security of transmission constraints are i= gnored and the model of the network [15] is sufficiently coarse. The incorp= oration of market considerations [10,11] complicates matters considerably.<= /p>

[1] S. Ahmed, A. King, G. Parija, "A Multi-Stage Stochastic Integer Prog= ramming Approach for Capacity Expansion under Uncertainty," Journal of Glob= al Optimization, Vol. 26, pp. 3=E2=80=9324, 2003.

[2] L. Baringo and A. J. Conejo, =E2=80=9CTransmission and Wind Power In= vestment,=E2=80=9D IEEE Transactions on Power Systems, Vol. 27 (2): 885-893= , 2012

[2] R. Hemmati, R. Hooshmand, A. Khodabakhshian, "Comprehensive review o= f generation and transmission expansion planning", IET Generation Transmiss= ion Distribution 7(2013) 955=E2=80=93964.

[3] S. R. Khuntia, B. W. Tuinema, J. L. Rueda, and M. A. M. M. van der M= eijden, =E2=80=9CTime-horizons in the planning and operation of transmissio= n networks: an overview=E2=80=9D, IET Generation Transmission Distribution,= Vol. 10 (4): 841=E2=80=93848, 2016.

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

[5] W. Li and R. Billinton, =E2=80=9CA minimum cost assessment method fo= r composite generation and transmission system expansion planning,=E2=80=9D= IEEE Transactions on Power Systems, Vol. 8(2): 628=E2=80=93635, 1993

[6] J. A. L=C3=B3pez, K. Ponnambalam, and V. H. Quintana, =E2=80=9CGener= ation and transmission expansion under risk using stochastic programming,= =E2=80=9D IEEE Transactions on Power Systems, Vol. 22(3), 1369=E2=80=931378= , 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, =E2=80=9CMINLP in tran= smission expansion planning,=E2=80=9D 2016 Power Systems Computation Confer= ence (PSCC), 1-8, June 2016

[9] M. Pereira, L. Pinto, S. Cunha, and G. Oliveira, =E2=80=9CA decompos= ition approach to automated generation/transmission expansion planning,=E2= =80=9D IEEE Transactions on Power Apparatus and Systems, Vol. 104(11), 3074= =E2=80=933083, 1985

[10] D. Pozo, E. Sauma, J. Contreras, =E2=80=9CA Three-Level Static MILP= Model for Generation and Transmission Expansion Planning,=E2=80=9C I= EEE Transactions on Power Systems, 10.1109/TPWRS.2012.2204073, 2013.

[11] J. H. Roh, M. Shahidehpour, and Y. Fu, =E2=80=9CMarket-based coordi= nation of transmission and generation capacity planning,=E2=80=9D IEEE Tran= sactions on Power Systems, Vol. 22(4), 1406=E2=80=931419, Nov. 2007

[12] M. Shahidehpour, =E2=80=9CInvesting in expansion: The many issues t= hat cloud electricity planning,=E2=80=9D IEEE Power and Energy Magazine, 14= -18, Jan 2004

[13] M. Shahidehpour, =E2=80=9CGlobal broadcast =E2=80=94 transmission p= lanning in restructured systems,=E2=80=9D IEEE Power and Energy Magazine., = Vol. 5(5), 18-20, Sep./Oct. 2007

[14] M. Shahidehpour, W. Tinney, and Y. Fu, =E2=80=9CImpact of security = on power system operation,=E2=80=9D IEEE Proceedings, Vol. 93(11), 2013 =E2= =80=93 2025, Nov. 2005

[15] Y. Scholz, Renewable Energy Based Electricity Supply At Low Costs = =E2=80=93 Development Of The Remix Model And Application For Europe, PhD Di= ssertation, German Aerospace Center (DLR), Institute of Technical Thermodyn= amics, 2012

[16] J. A. Taylor, F. S. Hover, =E2=80=9CLinear Relaxations for Transmis= sion System Planning,=E2=80=9C IEEE Transactions on Power Systems, Vo= l. 26(4): 2533=E2=80=932538, 2011

[17] A. H. van der Weijde and B. F. Hobbs, =E2=80=9CThe economics of pla= nning electricity transmission to accommodate renewables: Using two-stage o= ptimisation to evaluate flexibility and the cost of disregarding uncertaint= y,=E2=80=9D Energy Economics, Vol. 34(5), 2089-2101, Sept. 2012

Dr Jakub Marecek, IBM

Prof. Laureano Escudero, Universidad Rey Juan Carlos<= /span>

Dr Fabrizio Lacalandra, QuanTek