Preprint
Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis
Abstract
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 or 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.
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 or 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.
Citation
@article{doi:10.17170/kobra-202202015681,
author={Bley, Andreas and Hahn, Philipp},
title={Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis},
year={2021}
}
0500 Oax
0501 Text $btxt$2rdacontent
0502 Computermedien $bc$2rdacarrier
1100 2021$n2021
1500 1/eng
2050 ##0##http://hdl.handle.net/123456789/13584
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/13584=x R
4204 \$dPreprint
4170
5550 {{Netzwerk}}
5550 {{Design}}
5550 {{Mathematisches Problem}}
5550 {{Szenario}}
5550 {{Hauptkomponentenanalyse}}
7136 ##0##http://hdl.handle.net/123456789/13584
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2022-02-02T12:55:31Z 2022-02-02T12:55:31Z 2021-11-30 doi:10.17170/kobra-202202015681 http://hdl.handle.net/123456789/13584 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ robust network design scenario reduction principal component analysis 510 Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis Preprint 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 or 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 25 Seiten Kassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften Netzwerk Design Mathematisches Problem Szenario Hauptkomponentenanalyse submittedVersion Mathematische Schriften Kassel false </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt