Efficient nested solutions of the bipartite network interdiction problem

Michael V. Nehme; David P. Morton

Efficient nested solutions of the bipartite network interdiction problem

Michael V. Nehme, David P. Morton

Industrial Engineering and Management Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 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 language	English (US)
Title of host publication	IIE Annual Conference and Expo 2010 Proceedings
Publisher	Institute of Industrial Engineers
State	Published - Jan 1 2010
Event	IIE Annual Conference and Expo 2010 - Cancun, Mexico Duration: Jun 5 2010 → Jun 9 2010

Other

Other	IIE Annual Conference and Expo 2010
Country/Territory	Mexico
City	Cancun
Period	6/5/10 → 6/9/10

Keywords

Integer programming
Network interdiction
Stochastic programming
Submodularity

ASJC Scopus subject areas

Industrial and Manufacturing Engineering

Cite this

@inproceedings{9866bee4fec24325a5310119bba825e1,

title = "Efficient nested solutions of the bipartite network interdiction problem",

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.",

keywords = "Integer programming, Network interdiction, Stochastic programming, Submodularity",

author = "Nehme, {Michael V.} and Morton, {David P.}",

year = "2010",

month = jan,

day = "1",

language = "English (US)",

booktitle = "IIE Annual Conference and Expo 2010 Proceedings",

publisher = "Institute of Industrial Engineers",

note = "IIE Annual Conference and Expo 2010 ; Conference date: 05-06-2010 Through 09-06-2010",

}

TY - GEN

T1 - Efficient nested solutions of the bipartite network interdiction problem

AU - Nehme, Michael V.

AU - Morton, David P.

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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.

AB - 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.

KW - Integer programming

KW - Network interdiction

KW - Stochastic programming

KW - Submodularity

UR - http://www.scopus.com/inward/record.url?scp=84901049862&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84901049862&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84901049862

BT - IIE Annual Conference and Expo 2010 Proceedings

PB - Institute of Industrial Engineers

T2 - IIE Annual Conference and Expo 2010

Y2 - 5 June 2010 through 9 June 2010

ER -

Efficient nested solutions of the bipartite network interdiction problem

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this