Shortest‐path network interdiction

By E. Israeli, R. K. Wood. Networks, 2002

627 citations recorded by the source corpus.

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.

Subfields: Civil and Structural Engineering, Safety, Risk, Reliability and Quality, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c7c521e7cb8e5545b4f7fde62f9a581d30728e1b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Civil and Structural Engineering

In Safety, Risk, Reliability and Quality

In Statistics and Probability

Citations in the corpus

A bilevel mixed-integer program for critical infrastructure protection planning (2008, background): “The resulting fortification/interdiction problem can be described within a game theoretic framework as a leader–follower or Stackelberg game [26] and formulated as a bilevel programming problem, as detailed in the next section.”
Adversarial Attacks on Node Embeddings via Graph Poisoning (2018, background): “…structure to manipulate: information spread in a network (Khalil et al., 2014; Chen et al., 2016), user opinions (Chaoji et al., 2012; Amelkin & Singh, 2017), shortest paths (Phillips, 1993; Israeli & Wood, 2002), page rank scores (Cs ´ aji et al., 2014), and other metrics (Chan et al., 2014).”
Planning for Disruptions in Supply Chain Networks (2006, methodology): “The two multilevel models incorporate in the lower level the interdiction models described by Israeli and Wood [48] and by Wood [106], respectively.”
Analyzing the Vulnerability of Critical Infrastructure to Attack and Planning Defenses (2005, methodology): “See Israeli and Wood [25] for details on this model and solution techniques for it.”
Defending Critical Infrastructure (2006, background): “The upper bound from the relaxed master problem remains valid if we have not identiﬁed an optimal solution; if we have identiﬁed such a solution, the value of the bound is irrelevant.”
A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications (2017, background): “5) Defense Applications: Bilevel optimization has a number of applications in the defense sector [30], for example attacker–defender Stackelberg games [9], [34], [85], [125], [131], [132], [137].”
Models for nuclear smuggling interdiction (2007, background): “Generalizations of the k-most-vital arcs problem are considered in [25].”
Analysis of electric grid security under terrorist threat (2004, methodology): “The master problem incorporates super-valid inequalities (constraints that eliminate some solutions, but not all optimal ones, unless an optimal solution has already been identified [5]) to avoid repeating solutions.”