In this thesis we consider the Steiner tree packing problem (STP). For a graph G = (V, E) with positive integer capacities and non-negative weights on its edges, and a list of node sets (nets), the problem is to find a connection of nets which satisfies the edge capacity limits and minimizes the total weights. This problem arises in routing phase of VLSI design. We discuss several variants of practically relevant routing problems and give a short survey on the underlying technologies and design rules.
We focus on the switchbox routing problem in knock-knee model and formulate this problem as an integer programming using Steiner tree variables. To solve the linear programming relaxation that has exponentially many variables, we develop an efficient column generation procedure. Moreover, we devise a new primal-heuristic based on LP solution. Using the results, we develop a branch-and-price algorithm with column generation where a complete branching rule has been adopted. We test our algorithm on some standard test instances and compare the performances with the results using cutting plane approach. Computational results show that our algorithm is competitive to the cutting plane algorithm presented by Grotschel et al. and can be used to solve practically sized problems.
본 논문은 Steiner Tree Packing 문제를 다루고 있다. 이 문제는 어떤 주어진 그래프의 각 edge들이 용량과 비용을 가지고, 연결되어야 하는 노드들의 집합들이 주어진 상황에서, edge들의 용량제약을 만족시키면서 최소의 비용으로 연결하는 방법을 찾는 문제이다. 이러한 문제는 VLSI 설계 과정 중 배선 단계에서 발생하게 된다. 실제적으로 관련된 배선 문제와 기술적인 문제 및 설계 규칙에 대한 간단한 조사를 하였다.
본 논문은 몇 개의 배선 문제 중에서 knock-knee 방식으로 switchbox를 연결하는 문제를 Steiner 나무 변수를 사용하여 0-1 정수계획문제로 모형화 하였다. 변수가 지수적으로 많은 선형계획완화문제를 풀기위해서, 효율적인 열 생성기법을 제안하였다. 그리고, 선형계획완화 문제의 해를 이용하는 primal-heuristic을 개발하였다. 위의 결과들을 이용하여, 분지규칙, 열 생성기법을 종합하여 Branch-and-Price 알고리즘을 개발하였다. 몇 개의 기준 테스트 문제들에 적용해 본 결과 본 논문에서 제시한 알고리즘이 Grotshel 등이 제안한 분지절단 (Branch-and-Cut) 알고리즘과 대등하거나 나은 것으로 나타났고, 실제 문제에도 적용 가능함을 알 수 있었다.
