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

Abstract

본 논문은 ``강건 최대 흐름 네트워크 공격 문제의 최적화 기법``에 관해서 연구한 논문이다. 최대 흐름 네트워크 공격 문제란 제한된 네트워크에서, 마디 ``s``에서 마디 ``t``까지의 최대 흐름을 최소화하는 문제이다. 기존의 최대 흐름 네트워크 공격 문제는 확정적 모형이므로 모형을 보다 현실화 하기 위해서는 모형에 불확실성을 반영해야 한다. 따라서 우리는 본 논문에서 최대 흐름 네트워크 공격 문제에 강건 조합 최적화 기법을 활용하여 불확실성을 반영한 ``강건 최대 흐름 네트워크 공격 문제``의 모형을 제시한다. 그리고 보다 복잡해진 문제를 효율적으로 해결하기 위하여 조합적 Benders`` 절단 평면을 이용하여 최적해를 도출하는 알고리즘을 제안한다. 그리고 실험 결과를 첨부하여 알고리즘의 효율성을 입증한다.