Deterministic Network Interdiction

Abstract

Interest in network interdiction has been rekindled because of attempts to reduce the flow of drugs and precursor chemicals through river and road networks in South America. This paper considers a problem in which an enemy attempts to maximize flow through a capacitated network while an interdictor tries to minimize this maximum flow by interdicting (stopping flow on) network arcs using limited resources. This problem is shown to be NP-complete even when the interdiction of an arc requires exactly one unit of resource. New, flexible integer programming models are developed for the problem and its variations, and valid inequalities and a reformulation are derived to tighten the LP relaxation of some of these models. A small computational example from the literature illustrates a hybrid (partly directed and partly undirected) model and the usefulness of the valid inequalities and the reformulation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1993
Accession Number
ADA487308

Entities

People

  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Applied Mathematics
  • Computer Programming
  • Computers
  • Drug Interdiction
  • Inequalities
  • Information Operations
  • Integer Programming
  • Interdiction
  • Interdisciplinary Science
  • Mathematical Programming
  • Mathematics
  • Military Operations
  • Operations Research
  • South America
  • Systems Science

Readers

  • Operations Research