This thesis considers the problem of designing capacitated network with tree configuration (CTP). For a given set of nodes with their capacities, k types of link facilities with various characteristics, and wiring cost needed to connect each pair of nodes using each type of link facility, the problem is to find the tree network which satisfies the given traffic requirements between all pairs of nodes and minimizes total wiring cost.
We formulate (CTP) as an integer programming problem using path variables. To solve the linear programming relaxation which has exponentially many variables, we develop a polynomial-time column generation procedure. Moreover, to tighten the formulation, an efficient preprocessing procedure is devised and some classes of valid inequalities are found. Using the results, we develop a branch-and-cut algorithm with column generation where an efficient branching rule is adopted. Computational results show that the algorithm can solve practically-sized problems to optimality within reasonable time.
본 논문은 용량제약이 있는 트리망의 설계문제를 다루고 있다. 이 문제는, 용량제약이 있는 노드들과, 다양한 특성을 가지는 k 가지의 링크설비 그리고 각 노드의 짝들을 각 타입의 링크설비를 이용하여 연결하는데 필요한 비용이 주어진 상황에서, 모든 노드짝들 사이의 트래픽 요구량을 만족하면서 비용이 최소화되는 트리망을 찾는것이다.
본 논문에서는 위 문제를 경로변수를 사용하여 0-1 정수계획문제로 모형화 하였다. 변수가 지수적으로 많은 선형계획완화문제를 풀기위해서, 다항시간 열생성 기법을 고안하였다. 또한, 모형을 정수가능해들이 정의하는 볼록집합에 근사하게 하기위해서, 효율적인 선행처리기법을 제안하고 유효부등식들을 찾았다. 위의 결과들을 이용하여, 효율적인 분지규칙, 열생성기법을 종합하여 분지절단 알고리듬을 개발하였다. 다양한 자료들에 대해 실험해 본 결과, 이 알고리듬이 현실적인 크기의 문제의 최적해를 짧은 시간안에 구할 수 있음을 알 수 있었다.
