Two extended formulations for cardinality maximum flow network interdiction problem

We consider the maximum flow network interdiction problem in its cardinality case. There is an integer programming model for this problem by Wood (Math Comput Model 17 (1993), 1–18). Two types of valid inequalities have also been proposed (Altner et al., Oper Res Lett 38 (2010), 33–38 and Wood, Math Comput Model 17 (1993), 1–18) to strengthen the LP relaxation of the integer model. However, due to their combinatorial nature, the number of these inequalities are exponential. Here, we present an equivalent reformulation (extended formulation) for this problem which has a polynomial number of constraints. We also introduce new valid inequalities, and show that the corresponding reformulation of the LP relaxation of the integer model augmented with these inequalities, significantly decreases the integrality gap for a class of network interdiction problems with proven large integrality gaps. Numerical results for some benchmark as well as randomly generated instances are also reported.