A constrained binary knapsack approximation for shortest path network interdiction

作者：Yates Justin^*; Lakshmanan Kavitha

来源：Computers & Industrial Engineering, 2011, 61(4): 981-992.

DOI：10.1016/j.cie.2011.06.011

• Network interdiction
• Homeland security
• Approximation techniques
• Integer programming

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.

• 出版日期2011-11