A constrained binary knapsack approximation for shortest path network interdiction

A modified shortest path network interdiction model is approximated in this work by a constrained binary knapsack which uses aggregated arc maximum flow as the objective function coefficient. In the modified shortest path network interdiction problem, an attacker selects a path of highest non‐detection probability on a network with multiple origins and multiple available targets. A defender allocates a limited number of resources within the geographic region of the network to reduce the maximum network non‐detection probability between all origin‐target pairs by reducing arc non‐detection probabilities and where path non‐detection probability is modeled as a product of all arc non‐detection probabilities on that path. Traditional decomposition methods to solve the shortest path network interdiction problem are sensitive to problem size and network/regional complexity. The goal of this paper is to develop a method for approximating the regional allocation of defense resources that maintains accuracy while reducing both computational effort and the sensitivity of computation time to network/regional properties. Statistical and spatial analysis methods are utilized to verify approximation performance of the knapsack method in two real‐world networks.