A decomposition approach for stochastic shortest-path network interdiction with goal threshold
Summary: Shortest-path network interdiction, where a defender strategically allocates interdiction resource on the arcs or nodes in a network and an attacker traverses the capacitated network along a shortest \(s\)-\(t\) path from a source to a terminus, is an important research problem with potential real-world impact. In this paper, based on game-theoretic methodologies, we consider a novel stochastic extension of the shortest-path network interdiction problem with goal threshold, abbreviated as SSPIT. The attacker attempts to minimize the length of the shortest path, while the defender attempts to force it to exceed a specific threshold with the least resource consumption. In our model, threshold constraint is introduced as a trade-off between utility maximization and resource consumption, and stochastic cases with some known probability \(p\) of successful interdiction are considered. Existing algorithms do not perform well when dealing with threshold and stochastic constraints. To address the NP-hard problem, SSPIT-D, a decomposition approach based on Benders decomposition, was adopted. To optimize the master problem and subproblem iteration, an efficient dual subgraph interdiction algorithm SSPIT-S and a local research based better-response algorithm SSPIT-DL were designed, adding to the SSPIT-D. Numerical experiments on networks of different sizes and attributes were used to illustrate and validate the decomposition approach. The results showed that the dual subgraph and better-response procedure can significantly improve the efficiency and scalability of the decomposition algorithm. In addition, the improved enhancement algorithms are less sensitive and robust to parameters. Furthermore, the application in a real-world road network demonstrates the scalability of our decomposition approach.
- Shortest-path network interdiction
- A decomposition algorithm applied to planning the interdiction of stochastic networks
- Shortest path interdiction problem with arc improvement recourse: A multiobjective approach
- Assessing the effectiveness of \(k\)-shortest path sets in problems of network interdiction
- New solution approaches for the maximum-reliability stochastic network interdiction problem
- A bilevel mixed-integer program for critical infrastructure protection planning
- A survey on robustness in railway planning
- Algorithms for network interdiction and fortification games
- Deterministic network interdiction
- Evader interdiction: algorithms, complexity and collateral damage
- Generalized Benders decomposition
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- Interdicting a Nuclear-Weapons Project
- Maximizing the minimum source-sink path subject to a budget constraint
- Minimizing a stochastic maximum-reliability path
- On generalized Stackelberg strategies
- On short paths interdiction problems: Total and node-wise limited interdiction
- On the power of randomization in network interdiction
- Optimal Interdiction of Unreactive Markovian Evaders
- Pareto optimality, game theory and equilibria
- Protection of flows under targeted attacks
- Robust and adaptive network flows
- Shortest path network interdiction with asymmetric information
- Shortest-path network interdiction
- Stochastic network interdiction
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- The small-world phenomenon: an algorithmic perspective
- Two-Person Zero-Sum Games for Network Interdiction
- Assessing the effectiveness of \(k\)-shortest path sets in problems of network interdiction
- Heuristics for multi-stage interdiction of stochastic networks
- Reformulation and sampling to solve a stochastic network interdiction problem
- Shortest path network interdiction with asymmetric information
- Network interdiction through length-bounded critical disruption paths: a bi-objective approach
- The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms
- Shortest path network interdiction with asymmetric uncertainty
This page was built for publication: A decomposition approach for stochastic shortest-path network interdiction with goal threshold
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311034)
