|Title of host publication||Wiley Encyclopedia of Operations Research and Management Science|
|Editors||James J Cochran, Louis Anthony Cox, Jr, Pinar Keskinocak , Jeffrey P Kharoufeh, J Cole Smith|
|Publisher||John Wiley & Sons|
|State||Published - Feb 15 2011|
We describe discrete stochastic network interdiction of shortest-path, and maximum-reliability-path, networks. A nested “max–min” model is reformulated using duality and, if necessary, an equivalent penalty-based model. The resulting mixed-integer program is then amenable to solution by standard solvers. Special-purpose decomposition algorithms, and accompanying valid inequalities, are also developed, which permit solution of larger scale problem instances. Throughout the article, we point to important models that arise when key assumptions in our formulations are modified.