In this thesis, we solve the Steiner tree problem in graph using column generation technique. This algorithm is based on integer programming formulation for directed graph and based on path variables which can be generated in polynomial time. We improve the performance of the algorithm by adopting row-generation technique and stabilized column generation technique. We compare the performance of the algorithm with the branch-and-cut algorithm based on cut set constraint. The LP relaxations of our formulation and the cut-set based formulation provide the same lower bound on the optimal value. We compare the performance of both approaches in computation time, the number of generated cuts and columns. We use preprocessing for large test problems to reduce the problem size considerably. Test results on SteinLib benchmark problems are reported.
스타이너 나무 문제는 네트워크 설계와 관련되어 많은 관심을 받아왔고 빠른 시간 내에 최적 해를 찾기 위해 많은 관련된 접근 방법이 있다. 하지만 이 문제는 NP-hard로 문제의 크기가 커지면 쉽게 풀리지 않으며 큰 크기의 문제를 위한 효과적인 알고리즘은 아직 발견되지 않았다.
우리는 정수계획법을 통해 스타이너 나무 문제를 접근하였으며 열 생성 기법을 이용하였고 같은 lower bound를 가지는 절단평면 기법을 이용한 알고리즘과의 성능을 비교하였다. 방향성이 있는 그래프에서 해를 찾았고 초기 해를 찾기 위해 효과적인 휴리스틱 방법을 사용하였다.
알고리즘의 성능 개선을 위해 많은 방법을 시도하였다. 데이터를 전 처리과정을 거치며 크기를 줄임으로써 문제를 더 빠르게 풀 수 있게 하였으며 Stabilized 열 생성 기법을 이용하여 쌍대 문제의 해공간을 제어하며 최적해로 더 빠르게 수렴하도록 하였다.
실험을 위해 public ftp에서 데이터를 가져왔고 절단평면을 이용한 방식과 비교하였다. 이 알고리즘은 작은 크기의 문제에 대해서는 좋은 성능을 보이지만 크기가 조금만 더 커져도 매우 심한 퇴화 현상이 발생하며 매우 좋지 않은 성능을 보였다.
