Minimizing a stochastic maximum-reliability path

Feng Pan, David P. Morton

Research output: Contribution to journalArticlepeer-review

52 Scopus citations

Abstract

We consider a stochastic network interdiction problem in which the goal is to detect an evader, who selects a maximum-reliability path. Subject to a resource constraint, the interdictor installs sensors on a subset of the network's arcs to minimize the value of the evader's maximum-reliability path, i.e., to maximize the detection probability. When this decision is made, the evader's origin-destination pair is known to the interdictor only through a probability distribution. Our model is framed as a stochastic mixed-integer program and solved by an enhanced L-shaped decomposition method. Our primary enhancement is via a valid inequality, which we call a step inequality. In earlier work [Morton et al., IIE Trans 39 (2007), 3-14], we developed step inequalities for the special case in which the evader encounters at most one sensor on an origin-destination path. Here, we generalize the step inequality to the case where the evader encounters multiple sensors. In this more general setting, the step inequality is tightly coupled to the decomposition scheme. An efficient separation algorithm identifies violated step inequalities and strengthens the linear programming relaxation of the L-shaped method's master program. We apply this solution procedure with further computational enhancements to a collection of test problems.

Original languageEnglish (US)
Pages (from-to)111-119
Number of pages9
JournalNetworks
Volume52
Issue number3
DOIs
StatePublished - Oct 1 2008

Keywords

  • Network interdiction
  • Stochastic programming
  • Valid inequality

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Minimizing a stochastic maximum-reliability path'. Together they form a unique fingerprint.

Cite this