This thesis considers two types of path packing problems which arise in a telecommunication network. One is the bandwidth packing problem and the other is the primary path selection problem. It is shown that the latter can be transformed to the former. The bandwidth packing problem can be formulated as a 0-1 integer programming problem with exponentially many variables. After we initially formulate the problem by finding k-shortest paths for each call, we use the delayed column generation technique to solve the formulation optimally. We find minimal cover inequalities violated by the current solution and do lifting to strengthen the inequalities found. We add the constraints found to the formulation and use the column generation technique iteratively. The algorithm is tested on problems of several network configurations. Computational results show that the algorithm performs well in solving the bandwidth packing problem. Moreover, the approach can be used in solving other problems arising in communication networks which include path selection as subproblem.
본 논문은 호의 용량제한이 있는 통신 네트워크에서 콜의 경로를 선택하는 두 가지 유형의 문제를 다루고 있다. 첫번째 유형의 문제는 주어진 콜중에서 어떤 것을 선택하여 어느 경로로 선택된 콜들을 할당할 것인가이다. 다른 하나의 문제는 주어진 모든 콜들의 경로를 선택하여 할당하여 주는 것이다. 두번째 유형의 문제는 첫번째 유형으로 변환될 수 있음이 증명되었다. 콜의 경로선택 문제는 이진 정수계획 문제로 모형화 할 수 있지만 변수의 수가 네트워크의 크기에 대해서 기하급수적으로 증가한다. 따라서 우리는 각 콜에 대해서 k개의 최단 경로를 찾음으로써 선형계획 문제로 완화된 초기 모형을 구한다. 그리고 열생성 기법을 사용하여 초기 모형의 최적해를 구한다. 최적해가 정수가 아니면 해공간을 절단할 수 있는 제약식을 찾아서 모형에 추가한다. 그리고 다시 열생성기법을 통해서 확장된 문제의 최적해를 구한다. 위의 과정을 반복해서 수행한다. 위의 알고리즘을 여러 네트워크에 대해서 시험해 본 결과 빠른 시간내에 좋은 해를 발견하여, 이 알고리즘이 효율적인 것임이 입증되었다.
