XOR-Sampling for Network Design with Correlated Stochastic Events
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Optimizing Resilience in Large Scale NetworksProceedings of the AAAI Conference on Artificial Intelligence, 2016
- Enhancing ecosystem restoration efficiency through spatial and temporal coordinationProceedings of the National Academy of Sciences, 2015
- Rounded Dynamic Programming for Tree-Structured Stochastic Network DesignProceedings of the AAAI Conference on Artificial Intelligence, 2014
- A Scalable and Nearly Uniform Generator of SAT Witnesses2013
- Lagrangian Relaxation Techniques for Scalable Spatial Conservation PlanningProceedings of the AAAI Conference on Artificial Intelligence, 2012
- Modeling Stochastic Correlated Failures and their Effects on Network Reliability2011
- Pre-disaster investment decisions for strengthening a highway networkComputers & Operations Research, 2010
- Network Reliability With Geographically Correlated Failures2010
- On Modern Clause-Learning Satisfiability SolversJournal of Automated Reasoning, 2009
- The Sample Average Approximation Method for Stochastic Discrete OptimizationSIAM Journal on Optimization, 2002