Exact algorithms for solving a euclidean maximum flow network interdiction problem

Kelly M. Sullivan, J. Cole Smith

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We consider an interdiction problem that involves an operator (or defender) whose goal is to maximize flow from a source node to a sink node in some network that resides in Euclidean space. The problem we examine takes the perspective of an interdictor, who seeks to minimize the defender's maximum flow by locating a set of attacks that diminish arc capacities in accordance with the distance from the arc to the attack. Attacks are not restricted to node or arc locations, and can occur anywhere on the region in which the network is located. We refer to this problem as the Euclidean maximum flow network interdiction problem (E-MFNIP). We show that E-MFNIP is NP-hard, as it generalizes the maximum flow interdiction problem studied by Wood [47]. This article contributes two approaches to solving E-MFNIP based on solving a sequence of lower-bounding integer programs from which upper bounds can be readily obtained, and shows that these bounds are convergent. Computations on a set of test instances indicate that an approach based on space-discretization tends to converge much faster than one based on linearizing the nonlinear capacity functions. We demonstrate the application of our spacediscretization approach on a real geographical network.

Original languageEnglish (US)
Pages (from-to)109-124
Number of pages16
JournalNavigation, Journal of the Institute of Navigation
Volume64
Issue number2
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

Keywords

  • Bilevel optimization
  • Euclidean space
  • Global optimization
  • Integer programming
  • Network interdiction
  • Space-discretization

ASJC Scopus subject areas

  • Aerospace Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Exact algorithms for solving a euclidean maximum flow network interdiction problem'. Together they form a unique fingerprint.

  • Cite this