We describe a stochastic network interdiction problem in which an interdictor, subject to limited resources, installs radiation detectors at border checkpoints in a transportation network in order to minimize the probability that a smuggler of nuclear material can traverse the residual network undetected. The problems are stochastic because the smuggler's origin-destination pair, the mass and type of material being smuggled, and the level of shielding are known only through a probability distribution when the detectors are installed. We consider three variants of the problem. The first is a Stackelberg game which assumes that the smuggler chooses a maximum-reliability path through the network with full knowledge of detector locations. The second is a Cournot game in which the interdictor and the smuggler act simultaneously. The third is a "hybrid" game in which only a subset of detector locations is revealed to the smuggler. In the Stackelberg setting, the problem is NP-complete even if the interdictor can only install detectors at border checkpoints of a single country. However, we can compute wait-and-see bounds in polynomial time if the interdictor can only install detectors at border checkpoints of the origin and destination countries. We describe mixed-integer programming formulations and customized branch-and-bound algorithms which exploit this fact, and provide computational results which show that these specialized approaches are substantially faster than more straightforward integer-programming implementations. We also present some special properties of the single-country case and a complexity landscape for this family of problems. The Cournot variant of the problem is potentially challenging as the interdictor must place a probability distribution over an exponentially-sized set of feasible detector deployments. We use the equivalence of optimization and separation to show that the problem is polynomially solvable in the single-country case if the detectors have unit installation costs. We present a row-generation algorithm and a version of the weighted majority algorithm to solve such instances. We use an exact-penalty result to formulate a model in which some detectors are visible to the smuggler and others are not. This may be appropriate to model "decoy" detectors and detector upgrades. / text
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/7512 |
| Date | 27 May 2010 |
| Creators | Nehme, Michael Victor |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Format | electronic |
| Rights | Copyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. |
Page generated in 0.002 seconds