Identifying critical demand scenarios for the robust capacitated network design problem using principal component analysis

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.