This paper is organized into five sections: following the introduction, Section 2 formally introduces the max flow network interdiction problem with restructuring, describes properties on when restructuring will not increase the flow, and interprets these properties in the context of disrupting drug trafficking networks; Section 3 discusses how drug trafficking networks can be modeled as max flow network interdiction problems, and how the authors model when the network is able to restructure; Section 4 derives a column-and-constraint generation algorithm that utilizes partial information from previous iterations; Section 5 compares this algorithm to other column-and-constraint generation algorithms; Section 6 analyzes the results on drug trafficking networks; and Section 7 concludes the paper and discusses directions of future work.
The authors consider a new class of max flow network interdiction problems, where the defender is able to introduce new arcs to the network after the attacker has made their interdiction decisions. They prove properties of when this restructuring will not increase the value of the minimum cut, which has important practical interpretations for problems of disrupting drug trafficking networks. In particular, it demonstrates that disrupting lower levels of these networks will not impact their operations when replacing the disrupted participants is easy. For the bilevel mixed integer linear programming formulation of this problem, they devise a column-and-constraint generation (C&CG) algorithm to solve it. The authors’ approach uses partial information on the feasibility of restructuring plans and is shown to be orders of magnitude faster than previous C&CG methods, and they demonstrate that applying decisions from standard max flow network interdiction problems can result in significantly higher flows than interdictions that account for the restructuring. (Publisher Abstract Provided)