This thesis considers Maximum Flow Network Interdiction Problem (MFNIP), which is to minimize the maximum flow from node ‘s’ to node ‘t’ by interdicting the arcs with limited resources available in the capacitated directed network. We consider the case in which there are uncertainties in the amount of resources needed to attack the arcs. To solve the problem, we propose an algorithm using Combinatorial Benders’ Cuts. We report computational experiences using the algorithm on some grid networks.
본 논문은 '강건 최대 흐름 네트워크 공격 문제의 최적화 기법'에 관해서 연구한 논문이다. 최대 흐름 네트워크 공격 문제란 제한된 네트워크에서, 마디 's'에서 마디 't'까지의 최대 흐름을 최소화하는 문제이다. 기존의 최대 흐름 네트워크 공격 문제는 확정적 모형이므로 모형을 보다 현실화 하기 위해서는 모형에 불확실성을 반영해야 한다. 따라서 우리는 본 논문에서 최대 흐름 네트워크 공격 문제에 강건 조합 최적화 기법을 활용하여 불확실성을 반영한 '강건 최대 흐름 네트워크 공격 문제'의 모형을 제시한다. 그리고 보다 복잡해진 문제를 효율적으로 해결하기 위하여 조합적 Benders' 절단 평면을 이용하여 최적해를 도출하는 알고리즘을 제안한다. 그리고 실험 결과를 첨부하여 알고리즘의 효율성을 입증한다.
