Shortest-Path Network Interdiction

Abstract

We study the problem of interdicting the arcs in a network in order to maximize the shortest s-t path length "Interdiction" is an attack on an arc that destroys the arc or increases its effective length; there is a limited interdiction budget. We formulate this bilevel, max-min problem as a mixed-integer program (MIP), which can be solved directly, but we develop more efficient decomposition algorithms. One algorithm enhances Benders decomposition by adding generalized integer cutting planes, called "supervalid inequalities" (SVIs), to the master problem. A second algorithm exploits a unique set-covering master problem. Computational results demonstrate orders-of-magnitude improvements of the decomposition algorithms over direct solution of the MIP and show that SVIs also help solve the original MIP faster.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2002
Accession Number
ADA490133

Entities

People

  • Eltan Israeli
  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computer Programming
  • Computer Science
  • Dynamic Programming
  • Flow Network
  • Integer Programming
  • Interdiction
  • Linear Programming
  • Mathematical Programming
  • Military Applications
  • New York
  • Operations Research
  • Optimization
  • Two Dimensional
  • United States
  • United States Strategic Command

Fields of Study

  • Computer science

Readers

  • Operations Research