Expanding an electrical transmission network requires heavy investments that need to be carefully planned, often at a regional or national level. We study relevant theoretical and practical aspects of transmission expansion planning, set as a bilinear programming problem with mixed 0-1 variables. We show that the problem is NP-hard and that, unlike the so-called Network Design Problem, a transmission network may become more efficient after cutting-off some of its circuits. For this reason, we introduce a new model that, rather than just adding capacity to the existing network, also allows for the network to be re-designed when it is expanded. We then turn into different reformulations of the problem, that replace the bilinear constraints by using a “big-M” approach. We show that computing the minimal values for the “big-M” coefficients involves finding the shortest and longest paths between two buses. We assess our theoretical results by making a thorough computational study on real electrical networks. The comparison of various models and reformulations shows that our new model, allowing for re-design, can lead to sensible cost reductions.
Citation
DOI: 10.1007/s12667-010-0010-9