Algorithms for discrete and continuous multicommodity flow network interdiction problems

Churlzu Lim, J. Cole Smith

Research output: Contribution to journalArticle

128 Scopus citations

Abstract

We consider a network interdiction problem on a multicommodity flow network, in which an attacker disables a set of network arcs in order to minimize the maximum profit that can be obtained from shipping commodities across the network. The attacker is assumed to have some budget for destroying (or "interdicting") arcs, and each arc is associated with a positive interdiction expense. In this paper, we examine problems in which interdiction must be discrete (i.e., each arc must either be left alone or completely destroyed), and in which interdiction can be continuous (the capacities of arcs may be partially reduced). For the discrete problem, we describe a linearized model for optimizing network interdiction that is similar to previous studies in the field, and compare it to a penalty model that does not require linearization constraints. For the continuous case, we prescribe an optimal partitioning algorithm along with a heuristic procedure for estimating the optimal objective function value. We demonstrate on a set of randomly generated test data that our penalty model for the discrete interdiction problem significantly reduces computational time when compared to that consumed by the linearization model.

Original languageEnglish (US)
Pages (from-to)15-26
Number of pages12
JournalIIE Transactions (Institute of Industrial Engineers)
Volume39
Issue number1
DOIs
StatePublished - Jan 1 2007
Externally publishedYes

Keywords

  • Bilinear programming
  • Integer programming
  • Multicommodity flows
  • Network interdiction

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Algorithms for discrete and continuous multicommodity flow network interdiction problems'. Together they form a unique fingerprint.

  • Cite this