Aufsatz
Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis
Zusammenfassung
In this paper, we consider the single-commodity robust network design problem. Given an undirected graph with capacity installation costs on its edges and a set S of scenarios with associated flow balance vectors that represent different scenarios of node supplies and demands, the goal is to find integer edge capacities that minimize the total installation cost and permit a feasible single commodity flow for each scenario. This problem arises, for example, in the design of power networks, which are dimensioned to accommodate many different load scenarios. We propose a new method to identify a small subset S′ of the given scenarios, such that solving the robust network design problem for the smaller scenario set S′ leads to almost the same capacities as solving it for the full scenario set S. By considering only the scenarios in S′, the size of the model that needs to be solved can be reduced substantially, while the error introduced by neglecting the remaining scenarios is kept very small. Our method only employs simple techniques from statistical data analysis, namely principal component analysis (PCA), and convex hull computations in low dimensions. Thus, its computational effort is very small and it is easily applicable to more complex network design problems. We evaluate the effectiveness of the method in computational experiments for instances stemming from offshore power grid planning and telecommunication networks. Our results show that the proposed techniques are indeed well suited to identify small scenario subsets that lead to significantly reduced models with high quality solutions.
Zitierform
In: Networks Volume 84 / Issue 3 (2024-06-11) , S. 278-299 ; eissn:1097-0037Förderhinweis
Gefördert im Rahmen des Projekts DEALZitieren
@article{doi:10.17170/kobra-2024092310867,
author={Bley, Andreas and Hahn, Philipp},
title={Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis},
journal={Networks},
year={2024}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2024$n2024 1500 1/eng 2050 ##0##http://hdl.handle.net/123456789/16059 3000 Bley, Andreas 3010 Hahn, Philipp 4000 Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis / Bley, Andreas 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/16059=x R 4204 \$dAufsatz 4170 5550 {{Netzwerk}} 5550 {{Design}} 5550 {{Mathematisches Problem}} 5550 {{Szenario}} 5550 {{Hauptkomponentenanalyse}} 7136 ##0##http://hdl.handle.net/123456789/16059
2024-09-23T13:03:35Z 2024-09-23T13:03:35Z 2024-06-11 doi:10.17170/kobra-2024092310867 http://hdl.handle.net/123456789/16059 Gefördert im Rahmen des Projekts DEAL eng Namensnennung 4.0 International http://creativecommons.org/licenses/by/4.0/ principal component analysis robust network design scenario reduction 510 Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis Aufsatz In this paper, we consider the single-commodity robust network design problem. Given an undirected graph with capacity installation costs on its edges and a set S of scenarios with associated flow balance vectors that represent different scenarios of node supplies and demands, the goal is to find integer edge capacities that minimize the total installation cost and permit a feasible single commodity flow for each scenario. This problem arises, for example, in the design of power networks, which are dimensioned to accommodate many different load scenarios. We propose a new method to identify a small subset S′ of the given scenarios, such that solving the robust network design problem for the smaller scenario set S′ leads to almost the same capacities as solving it for the full scenario set S. By considering only the scenarios in S′, the size of the model that needs to be solved can be reduced substantially, while the error introduced by neglecting the remaining scenarios is kept very small. Our method only employs simple techniques from statistical data analysis, namely principal component analysis (PCA), and convex hull computations in low dimensions. Thus, its computational effort is very small and it is easily applicable to more complex network design problems. We evaluate the effectiveness of the method in computational experiments for instances stemming from offshore power grid planning and telecommunication networks. Our results show that the proposed techniques are indeed well suited to identify small scenario subsets that lead to significantly reduced models with high quality solutions. open access Bley, Andreas Hahn, Philipp doi:10.1002/net.22236 Netzwerk Design Mathematisches Problem Szenario Hauptkomponentenanalyse publishedVersion eissn:1097-0037 Issue 3 Networks 278-299 Volume 84 false
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden: