Convex hull representation of the deterministic bipartite network interdiction problem

Kelly M. Sullivan, J. Cole Smith, David P. Morton

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

We consider a version of the stochastic network interdiction problem modeled by Morton et al. (IIE Trans 39:3-14, 2007) in which an interdictor attempts to minimize a potential smuggler's chance of evasion via discrete deployment of sensors on arcs in a bipartite network. The smuggler reacts to sensor deployments by solving a maximum-reliability path problem on the resulting network. In this paper, we develop the (minimal) convex hull representation for the polytope linking the interdictor's decision variables with the smuggler's for the case in which the smuggler's origin and destination are known and interdictions are cardinality-constrained. In the process, we propose an exponential class of easily-separable inequalities that generalize all of those developed so far for the bipartite version of this problem. We show how these cuts may be employed in a cutting-plane fashion when solving the more difficult problem in which the smuggler's origin and destination are stochastic, and argue that some instances of the stochastic model have facets corresponding to the solution of NP-hard problems. Our computational results show that the cutting planes developed in this paper may strengthen the linear programming relaxation of the stochastic model by as much as 25 %.

Original languageEnglish (US)
Pages (from-to)349-376
Number of pages28
JournalMathematical Programming
Volume145
Issue number1-2
DOIs
StatePublished - Jun 2014
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Convex hull representation of the deterministic bipartite network interdiction problem'. Together they form a unique fingerprint.

Cite this