Efficient nested solutions of the bipartite network interdiction problem

Michael V. Nehme, David P. Morton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We describe a stochastic network interdiction model for deploying radiation detectors at border checkpoints to detect smugglers of nuclear material. The model is stochastic because the smuggler's origin-destination pair is known only through a probability distribution when the detectors are installed. We formulate a mixed-integer program for the special case in which we can only install detectors at border checkpoints of either the origin or the destination country. While the problem is strongly NP-hard, we describe a family of instances which may be solved in polynomial time, and show that the solutions to this family are nested.

Original languageEnglish (US)
Title of host publicationIIE Annual Conference and Expo 2010 Proceedings
PublisherInstitute of Industrial Engineers
StatePublished - Jan 1 2010
EventIIE Annual Conference and Expo 2010 - Cancun, Mexico
Duration: Jun 5 2010Jun 9 2010

Other

OtherIIE Annual Conference and Expo 2010
CountryMexico
CityCancun
Period6/5/106/9/10

Keywords

  • Integer programming
  • Network interdiction
  • Stochastic programming
  • Submodularity

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Efficient nested solutions of the bipartite network interdiction problem'. Together they form a unique fingerprint.

Cite this