We consider the problem of establishing an optimal link capacity expansion plan over multiple periods on the telecommunication network that uses a Digital Cross-connect System (DCS) at each node. It is assumed that predetermined working channels on each link of the network are given for each period. Each link must have sufficient channel capacities to ensure the working channels and spare channels that are needed to restore the traffic when a link fails. We give an integer programming model for this problem which determines the number of facilities to be installed on each link to meet the aggregated requirements of working and spare channels at each period. We proposed a branch-and-cut algorithm for this problem which applies the cutting plane approach at each node of the branch-and-bound tree. Computational results show that the algorithm solves all randomly generated problems optimally in reasonable time bound.
본 논문은 DCS를 사용하는 통신망의 다기간의 용량 확장 계획 문제에 대한 연구이다. 주어진 각 링크의 운용 용량(working channels)을 만족시키며, 임의의 기간에 하나의 링크 장애 시에도 해당 링크의 traffic을 복구할 수 있도록 하는 여유 용량(spare channels)을 포함하여 매기간 각 링크에 설치할 링크 장비의 수를 총 설치비용이 최소화 되도록 결정한다.
본 논문에서는 위 문제의 정수 계획법 모형을 제시하였다. 제시된 정수 계획 모형의 선형 완화 문제를 해결하기 위해서 유효한 부등식을 찾고, 제약식 생성 기법과 분지, 절단을 이용한 알고리즘을 개발하였다. 여러 실험 데이타에 대하여 실험한 결과 만족할 만한 시간에 최적해를 찾을 수 있었다.
