A decomposition algorithm applied to planning the interdiction of stochastic networks

We describe the application of a decomposition based solution method to a class of network interdiction problems. The problem of maximizing the probability of sufficient disruption of the flow of information or goods in a network whose characteristics are not certain is shown to be solved effectively by applying a scenario decomposition method developed by Riis and Schultz [Comput Optim Appl 24 (2003), 267-287]. Computational results demonstrate the effectiveness of the algorithm and design decisions that result in speed improvements. (c) 2005 Wiley Periodicals, Inc.