Network Interdiction and Stochastic Integer Programming

by Woodruff, David L.

• ISBN13: 9781402073021
• ISBN10: 140207302X
• Format: Hardcover
• Copyright: 2002-11-01
• Publisher: Kluwer Academic Pub

Summary

The Network Interdiction Problem has a wide variety of applications in areas such as transportation, but more recently and very prominently, it has applications in the communications area. Network Interdiction and Stochastic Integer Programming focuses on problems associated with protecting and attacking computer, transportation, and social networks. These research areas gain importance as the world becomes more dependent on interconnected systems. Optimization models that address the stochastic nature of the problems are an important part of the book and it contains discussion of recent efforts to provide methods for addressing stochastic mixed integer programs. The book is organized with interdiction papers first and the stochastic programming papers in the second part. See the foreword by Roger Wets for further details on the topical coverage. Each chapter represents state-of-the-art research and all chapters have been carefully peer-reviewed.

Table of Contents

Preface	vii
Contributing Authors	viii
Foreword	ix
Roger J-B. Wets
Interdicting Smuggled Nuclear Material	1	(20)
Feng Pan
William S. Charlton
David P. Morton
A Stochastic Network Interdiction Model	5	(5)
Complexity	10	(2)
Application to Smuggling Out of a Single Country	12	(4)
Summary	16	(1)
Acknowledgements	17	(4)
Enumerating Near-Min s-t Cuts	21	(30)
Ahmet Balciglu
R. Kevin Wood
Preliminaries	25	(1)
Theoretical Results	26	(11)
Computational Results	37	(8)
Conclusions and Recommendations	45	(6)
A Decomposition-Based Approximation for Network Inhibition	51	(18)
Carl Burch
Robert Carr
Sven Krumke
Madhav Marathe
Cynthia Phillips
Eric Sundberg
Introduction	52	(4)
A Mixed-Integer Program for Network Inhibition	56	(1)
The Pseudo-approximation Algorithm	57	(2)
Decomposition	59	(5)
Geometry	64	(2)
Extensions	66	(3)
Interdicting Stochastic Networks	69	(16)
Raymond Hemmecke
Rudiger Schultz
David L. Woodruff
Introduction	70	(3)
Example	73	(3)
A Special Case: Disconnection as the Threshold	76	(2)
Benchmarks	78	(3)
Conclusions	81	(4)
Stochastic Batch-Sizing	85	(20)
Guglielmo Lulli
Suvrajeet Sen
Stochastic Batch-Sizing Formulations	88	(4)
Algorithmic approaches for Stochastic Batch-Sizing	92	(3)
Computational Results	95	(3)
Solutions from Alternative Models	98	(3)
Conclusions	101	(4)
Disjunctive Decomposition with Set Convexification	105	(1)
Suvrajeet Sen
Julia L. Higle
Lewis Ntaimo
Background	106	(9)
An Illustration of the D2 Algorithm	115	(8)
Conclusions	123