The Network Diversion Problem is to find a set of links with minimum cost in the connected directed graph so that eliminating this set guarantees that any flows from a source node to a sink node include at least one link from a predetermined set. We extend this problem. The extended problem has many source nodes or many sink nodes, so it has many flow from source node to sink node. We call this extended problem as the Multi-flow Network Diversion Problem. We propose an optimization algorithm for the Network Diversion Problem and the Multi-flow Network Diversion Problem by using combinatorial Benders’ cut. Computational results are reported.
네트워크 운용에 있어서 출발지와 도착지가 있을 때 두 지점간의 흐름이 반드시 특정 구간들 중 한 구간 이상을 지나도록 하기 위하여 최소의 비용으로 특정 구간들을 제외한 다른 구간들을 차단해야 하는 경우가 발생할 수 있는데 이러한 문제를 네트워크 전환 문제(Network Diversion Problem)라고 한다. 또한 이 문제가 확장되어 출발지와 도착지가 여러 개 일 때 모든 출발지에서 나온 흐름들이 특정 구간들 중 어느 한 구간을 거쳐 모든 도착지들로 들어갈 수 있도록 하기 위하여 최소의 비용으로 특정 구간들을 제외한 다른 구간들을 차단하는 문제가 발생할 수 있는데 이를 다 흐름 네트워크 전환 문제(Multi-flow Network Diversion Problem)라고 한다.
본 논문에서는 이러한 문제를 해결하기 위해 조합적 Benders’ 절단평면을 이용한 알고리즘을 제시하였다. 우선 조합적 Benders’ 절단평면의 원리 및 방법에 대하여 알아보았고, 이를 토대로 네트워크 전환 문제와 다 흐름 네트워크 전환 문제를 해결하기 위한 조합적 Benders’ 절단평면을 이용한 알고리즘을 제안하였다.
제안된 알고리즘을 이용해 격자형 그래프와 별형 그래프에 대하여 실험을 수행해 본 결과 다 흐름 네트워크 문제의 경우 보다 좋은 성능을 발휘함을 알 수 있었다.
