강건 최대 흐름 네트워크 공격 문제의 최적화 해법

Abstract

This paper considers maximum flow network interdiction problem (MFNIP), which is to minimize the maximum flow from a node to another node by interdicting the arcs with limited resources available in the capacitated directed network. To reflect the uncertainties in the amount of resources needed to attack, a robust maximum flow network interdiction problem was designed through the robust optimization technique. In order to solve the problem, an algorithm using combinatorial Benders’ cuts was proposed. The computational experiences were reported by using the algorithm on randomly generated grid networks.