  Modern society is critically dependent on the services provided by engineered
infrastructure networks. When natural disasters (e.g. Hurricane Sandy) occur,
the ability of these networks to provide service is often degraded because of
physical damage to network components. One of the most critical of these
networks is electric power, with medium voltage distribution circuits often
suffering the most severe damage. However, well-placed upgrades to these
distribution grids can greatly improve post-event network performance. We
formulate an optimal electrical distribution grid design problem as a
two-stage, stochastic mixed-integer program with damage scenarios from natural
disasters modeled as a set of stochastic events. We develop and investigate the
tractability of an exact and several heuristic algorithms based on
decompositions that are hybrids of techniques developed by the AI and
operations research communities. We provide computational evidence that these
algorithms have significant benefits when compared with commercial,
mixed-integer programming software.
