Show simple item record
dc.rightsUrheberrechtlich geschützt
dc.subjectrobust network designeng
dc.subjectscenario reductioneng
dc.subjectprincipal component analysiseng
dc.titleIdentifying critical demand scenarios for the robust capacitated network design problem using principal component analysiseng
dcterms.abstractIn 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.eng
dcterms.accessRightsopen access
dcterms.creatorBley, Andreas
dcterms.creatorHahn, Philipp
dcterms.extent25 Seiten
dc.contributor.corporatenameKassel, Universität Kassel, Fachbereich Mathematik und Naturwissenschaften
dc.subject.swdMathematisches Problemger
dcterms.source.seriesMathematische Schriften Kassel

Files in this item


This item appears in the following Collection(s)

Show simple item record