The K-group maximum-flow network-interdiction problem

Abstract

We study the K-group network-interdiction problem (KNIP) in which a "network user" attempts to maximize flow among K >/= 3 "node groups", while an "interdictor" interdicts (destroys) network arcs, using limited interdiction resources, to minimize this maximum flow. We develop two models to solve or approximately solve KNIP. The multi-partition network-interdiction model (MPNIM) is an approximating model. It partitions the node set N into K different subsets, each containing one prespecified node group, and interdicts arcs using limited resources so that the total capacity of uninterdicted arcs crossing between subsets is minimized. The multi-commodity network-interdiction model (MCNIM) explicitly minimizes the maximum amount of flow that can potentially be moved among node groups using K single-commodity flow models connected by joint capacity constraints. It is a min-max model but is converted into an equivalent integer program MCNIM-IP. Both MPNIM and MCNIM-IP are tested using four artificially constructed networks with up to 126 nodes, 333 arcs, K = 5, and 20 interdictions allowed. Using a 333 MHz Pentium II personal computer, maximum solution times are 563.1 seconds for MPNIM but six of 16 MCNIM-IP problems cannot be solved in under 3,600 seconds.