KIT | KIT-Bibliothek | Impressum | Datenschutz

Complexity of transmission network expansion planning NP-hardness of connected networks and MINLP evaluation

Oertel, David 1; Ravi, R.
1 Karlsruher Institut für Technologie (KIT)

Abstract (englisch):

Transmission network expansion planning in its original formulation is NP-hard due to the subproblem Steiner trees, the minimum cost connection of an initially unconnected network with mandatory and optional nodes. By using electrical network theory we show why NP-hardness still holds when this subproblem of network design from scratch is omitted by considering already (highly) connected networks only. This refers to the case of extending a long working transmission grid for increased future demand. It will be achieved by showing that this case is computationally equivalent to 3-SAT. Additionally, the original mathematical formulation is evaluated by using an appropriate state-of-the-art mixed integer non-linear programming solver in order to see how much effort in computation and implementation is really necessary to solve this problem in practice.

DOI: 10.1007/s12667-013-0091-3
Zitationen: 5
Zitationen: 5
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2014
Sprache Englisch
Identifikator ISSN: 1868-3967, 1868-3975
KITopen-ID: 1000069183
Erschienen in Energy systems
Verlag Springer
Band 5
Heft 1
Seiten 179-207
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page