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.

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 Scopus
OpenAlex
Dimensions

Originalveröffentlichung
DOI: 10.1007/s12667-013-0091-3
Scopus
Zitationen: 5
Dimensions
Zitationen: 5
Seitenaufrufe: 129
seit 12.05.2018
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page