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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A DCA Approach for a Maximum Flow Network Interdiction Problem

  • Hoai An Le Thi,
  • Thi Minh Tam Nguyen

摘要

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.