Earthquake Scenario Reduction by Symmetry Reasoning

A recently identified problem is that of finding an optimal investment plan for a transportation network, given that a disaster such as an earthquake may destroy links in the network. The aim is to strengthen key links to preserve the expected network connectivity. A network based on the Istanbul highway system has thirty links and therefore a billion scenarios, but it has been estimated that sampling a million scenarios gives reasonable accuracy. In this paper we use symmetry reasoning to reduce the number of scenarios to a much smaller number, making sampling unnecessary. This result can be used to facilitate metaheuristic and exact approaches to the problem.