• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Two-person games for stochastic network interdiction : models, methods, and complexities

Nehme, Michael Victor 27 May 2010 (has links)
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

Page generated in 0.1743 seconds