XOR-Sampling for Network Design with Correlated Stochastic Events
This work addresses network design under correlated stochastic events, which is more realistic than independent assumptions, but is incremental as it builds on existing SAA methods with a new sampler.
The paper tackles the problem of optimizing network protection strategies under correlated edge failures, using Markov Random Fields to model correlations and a Sample Average Approximation algorithm with XOR sampling. Experimental results on real road networks show that XOR sampling yields higher quality policies with lower variance compared to Gibbs sampling.
Many network optimization problems can be formulated as stochastic network design problems in which edges are present or absent stochastically. Furthermore, protective actions can guarantee that edges will remain present. We consider the problem of finding the optimal protection strategy under a budget limit in order to maximize some connectivity measurements of the network. Previous approaches rely on the assumption that edges are independent. In this paper, we consider a more realistic setting where multiple edges are not independent due to natural disasters or regional events that make the states of multiple edges stochastically correlated. We use Markov Random Fields to model the correlation and define a new stochastic network design framework. We provide a novel algorithm based on Sample Average Approximation (SAA) coupled with a Gibbs or XOR sampler. The experimental results on real road network data show that the policies produced by SAA with the XOR sampler have higher quality and lower variance compared to SAA with Gibbs sampler.