KIT | KIT-Bibliothek | Impressum
DOI: 10.1007/s12667-013-0091-3

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

Oertel, David; Ravi, R.

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
Jahr 2014
Sprache Englisch
Identifikator ISSN: 1868-3967, 1868-3975
KITopen ID: 1000069183
Erschienen in Energy systems
Band 5
Heft 1
Seiten 179-207
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page