Shortest-path network interdiction

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‐i...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2002-09, Vol.40 (2), p.97-111
Main Authors: Israeli, Eitan, Wood, R. Kevin
Format: Article
Language:English
Subjects:
Applied sciences
Benders decomposition
bilevel program
Exact sciences and technology
interdiction
shortest paths
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. Published 2002 Wiley Periodicals, Inc.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.10039