Premium
Shortest‐path network interdiction
Author(s) -
Israeli Eitan,
Wood R. Kevin
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10039
Subject(s) - interdiction , shortest path problem , benders' decomposition , integer (computer science) , decomposition , path (computing) , computer science , mathematical optimization , integer programming , set (abstract data type) , column generation , decomposition method (queueing theory) , arc (geometry) , exploit , algorithm , mathematics , theoretical computer science , discrete mathematics , engineering , ecology , geometry , graph , computer security , biology , programming language , aerospace engineering
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.