Reducing the Vulnerability of a Network Through Investment: Decision Dependent Link Failures.

We consider a problem that arises in disaster-related strategic planning: investing in the links of a stochastic network to improve its expected post-disaster performance. We are given a network whose links are subject to random failures, where the failure probability of a link is reduced by investing in the link. The operational links define a network realization, in which a specified pair of origin-destination (O-D) nodes need to be connected with a shortest path. There is a fixed penalty cost for any network realization that does not have connectivity between the O-D nodes. Our objective is to allocate a given budget to the links of the network such that the expected shortest path between the O-D nodes is minimized. We formulate the problem as a two-stage stochastic integer program with recourse, and propose a solution procedure by optimizing the expected shortest path over the connected network realizations, subject to a bound on the probability of disconnected realizations. In the proposed iterative procedure, given a feasible investment decision, we characterize the benefit from investing in a particular link by measuring the improvement in the expected shortest path.