Cutting plane approach for the maximum flow interdiction problem
研究最大流阻断问题，提出一种迭代割平面算法，在分支切割框架下高效求解，实验表明该方法在多数测试实例上优于直接求解。
The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.