Maximum dynamic network flow interdiction problem: New formulation and solution procedures

• We introduce the dynamic version of the maximum-flow network interdiction problem.
• We model the above problem using temporally repeated flows.
• We solve the model, using Benders’ decomposition algorithm.
• We try to improve Benders’ decomposition algorithm using most vital arcs.
• We report some computational results for several instances.

We consider the dynamic version of the maximum flow network interdiction problem; that is, we assume a positive number is assigned to each arc which indicates the traversal time of the flow through that arc. We also assume that an intruder uses a single resource with limited budget to interrupt the flow of a single commodity through the network within a given time limit of T. A new formulation based on the concept of Temporally Repeated Flow (TRF) is presented. The problem is then solved using Benders’ decomposition. Another solution method, based on the most vital arcs in a network is also discussed. Finally, some computational results are reported.