Premium
Dynamic shortest‐path interdiction
Author(s) -
Sefair Jorge A.,
Smith J. Cole
Publication year - 2016
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.21712
Subject(s) - interdiction , computer science , path (computing) , shortest path problem , node (physics) , mathematical optimization , set (abstract data type) , dynamic programming , longest path problem , algorithm , computer network , theoretical computer science , mathematics , graph , structural engineering , engineering , programming language , aerospace engineering
We study a dynamic network game between an attacker and a user. The user wishes to find a shortest path between a pair of nodes in a directed network, and the attacker seeks to interdict a subset of arcs to maximize the user's shortest‐path cost. In contrast to most previous studies, the attacker can interdict arcs any time the user reaches a node in the network, and the user can respond by dynamically altering its chosen path. We assume that the attacker can interdict a limited number of arcs, and that an interdicted arc can still be traversed by the user at an increased cost. The challenge is therefore to find an optimal path (possibly repeating arcs in the network), coupled with the attacker's optimal interdiction strategy (i.e., which arcs to interdict and when to interdict them). We propose an exact exponential‐state dynamic‐programming algorithm for this problem, which can be reduced to a polynomial‐time algorithm in the case of acyclic networks. We also develop lower and upper bounds on the optimal objective function value based on classical interdiction and robust optimization models, or based on an exact solution to variations of this problem. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 315–330 2016