A DCA Approach for a Maximum Flow Network Interdiction Problem
摘要
We investigate an approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for solving a maximum flow network interdiction problem. In this problem, an interdictor seeks to completely destroy a set of arcs in a network so as to minimize both the post-interdiction maximum flow and the total interdiction cost. We formulate the problem as a bilevel program with binary upper-level variables in which the objective function is the sum of a linear function and the value function of a linear program. By using an exact penalty function, we recast the bilevel optimization problem as a standard DC program and propose an appropriate DCA scheme to solve it. Numerical experiments on some rectangular grid networks illustrate the efficiency of our algorithm.