Efficient nested solutions of the bipartite network interdiction problem

Michael V. Nehme, David P. Morton

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

4 Scopus citations


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


OtherIIE Annual Conference and Expo 2010


  • Integer programming
  • Network interdiction
  • Stochastic programming
  • Submodularity

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


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

Cite this