We consider several routing and capacity assignment problems for the design of current and future fiber-optic telecommunication networks, specifically for interoffice transmission networks. We present formulations of the problems and algorithms for them which are based on the integer programming approaches.
First, we consider the primary path selection and working capacity assignment problem (PWP) for the design of current synchronous transmission networks. Given an undirected physical network, a set of selected pairs of nodes, the traffic requirement for each selected pairs of nodes, and one or more types of link facilities with discrete capacity and cost structure, (PWP) is to determine a path from a given set of candidate primary paths for each pair of nodes and the number of each type of link facilities to be installed on each link such that all the traffic requirements can be routed on the selected paths simultaneously at minimum installation costs. We present an integer programming formulation of (PWP), and then derive valid inequalities which can be used to tighten the LP relaxation of the proposed integer programming formulation of (PWP). Especially, we develop a new cut generation scheme which can generate valid inequalities for a specific knapsack problem arising from the capacity constraint on a link. We also customize the known valid inequalities. Using these results, we develop a branch-and-cut algorithm to solve (PWP) to optimality. Computational results show that the proposed cut generation scheme significantly enhance the performance of the algorithm.
Second, we consider an integer programming based optimization algorithm to solve the spare capacity assignment problem (SCAP) for the design of current synchronous transmission networks. Given predetermined working channels on each link of the network, the problem is to determine the spare capacity that should be added on each link to ensure rerouting of the traffic in case of a link failure. We propose an integer programming model with multiple types of link facilities which determines not only the spare capacity on each link but also the number of each type of link facilities needed to be installed on each link to meet the aggregated requirements of working and spare channels. The objective is to minimize the total installation cost. We propose a branch-and-cut algorithm to solve (SCAP). To solve the LP relaxation of the problem, an efficient constraint generation routine was devised. Moreover, some strong valid inequalities were found and used to strengthen the formulation. Computational results show that the algorithm can solve real world problems to optimality within a reasonable time.
Third, we study the ring loading problem with integer demand splitting (RLP) which arises in the design of SDH/SONET (Synchronous Digital Hierarchy/Synchronous Optical NETworks) bidirectional Self-Healing Rings from a theoretical point of view. (RLP) is given with a ring network in which the traffic requirement, given as an integer number of basic units, between each selected pair of nodes must be routed on it. Each traffic requirement can be routed around both directions on the ring network while splitting each traffic requirement in two directions only by integer. (RLP) is to find an optimal routing of each traffic requirement which minimizes the capacity requirement. We first present an integer programming formulation of (RLP) and characterize every extreme point solution to the LP relaxation of the formulation. We also show that the difference between the optimal objective value of the LP relaxation and that of (RLP) is at most one by constructing a feasible solution to (RLP) from an optimal solution to the LP relaxation which has fractional coordinates. Then, we present a strengthened linear program whose size is bounded by a polynomial function of the number of nodes and the number of selected pairs of nodes, which gives the optimal objective value of (RLP).
Finally, we consider two routing and wavelength assignment problems(RWA) in WDM (Wavelength Division Multiplexing) all-optical network employing wavelength routing. We are given an undirected physical network, a set of selected pairs of nodes, the number of required connections for each selected pair of nodes, and a set of available wavelengths. A required connection between a pair of nodes is realized on the given network by establishing a path between that pair of nodes (routing) and assigning a specific wavelengths to the path (wavelength assignment). The first problem (RWA1) is to realize as many connections as possible under the constraint that the paths which share a common link of the given network should be assigned to different wavelengths. The second problem (RWA2) is to realize all the given required connections on the given network under the same constraint as that in (RWA1). The objective is to minimize the number of required wavelengths. We present integer programming formulations for (RWA1) and (RWA2) each of which is decomposed into a master problem and a column generation problem. We develop a branch-and-price algorithm to solve the column generation problem to optimality. We also develop greedy-type heuristic algorithms for (RWA1) and (RWA2). Using the results, we propose algorithms for (RWA1) and (RWA2), which are based on the column generation and branch-and-bound scheme. Though the proposed algorithms can not guarantee optimal solutions to (RWA1) and (RWA2), computational results show that they can yield provably good solutions within a reasonable time.
본 논문에서는 국간광전송망 설계를 위한 경로설정 및 용량할당문제들에 대한 정수계획모형과 정수계획기법에 기초한 해법을 제시하고 있다.
첫째, 현재의 동기식 기간전송망 설계를 위한 주경로설정 및 운용용량할당문제를 연구하였다. 이 문제는 물리적인 관로망, 수요노드쌍들의 집합, 각 수요쌍별 수요, 그리고 이산적인 용량과 비용구조를 가지는 여러 종류의 링크장비들이 주어졌을 때, 각 수요쌍별로 미리 주어진 후보 주경로들 중에서 하나의 경로를 결정하고, 모든 수요쌍들이 정해진 주경로를 통하여 동시에 수요를 전달할 수 있도록 최소의 비용으로 각 링크에 설치할 각 종류의 링크장비의 설치개수를 결정하는 문제이다. 본 연구에서는 이 문제에 대한 정수계획모형을 제시하고, 선형계획완화문제를 강화할 수 있는 유효부등식을 제안한다. 특히, 각 링크의 용량제약식으로 부터 유효부등식을 생성할 수 있는 새로운 방안을 제시하였다. 또한, 기존의 연구에서 알려진 부등식들을 특화시켜 사용하였다. 이러한 결과를 종합하여, 이 문제의 최적해를 구할 수 있는 분지-절단 해법을 제시하였다. 전산실험을 수행한 결과, 본 연구에서 제안된 유효부등식의 생성 방안이 해법의 성능을 상당히 개선시킨다는 것을 알 수 있었다.
둘째, 현재의 동기식 기간전송망 설계와 관련하여, 전송망에 발생할 수 있는 링크장애에 대비한 여유용량할당문제를 연구하였다. 이 문제는 물리적인 관로망, 각 링크별로 할당된 운용채널, 그리고 이산적인 용량과 비용구조를 가지는 여러 종류의 링크장비들이 주어졌을 때, 한 번에 어떤 하나의 링크가 끊어지더라도 끊어진 링크에 할당된 운용채널을 우회시켜 복구할 수 있도록, 최소의 비용으로 각 링크에 설치하여야 할 각 종류별 링크장비의 설치개수를 결정하는 문제이다. 본 연구에서는 이 문제에 대한 정수계획모형을 제시하고, 이 문제의 최적해를 구할 수 있는 분지-절단 해법을 제시하였다. 이를 위해, 먼저, 제약식의 수가 지수적으로 많은 선형계획완화문제를 해결하기 위해 제약식을 동적으로 생성할 수 있는 방안을 강구하였고, 또한, 추가적인 유효부등식을 제안하였다. 전산실험을 수행한 결과, 본 연구에서 제시한 분지--절단 해법이 실제 문제에 대한 최적해를 빠른 시간내에 구할 수 있다는 것을 알 수 있었다.
셋째, 양방향 자가복구링의 용량을 결정하는 문제를 이론적인 관점에서 연구하였다. 이 문제는 하나의 링형망과 수요노드쌍들의 집합 및 각 수요쌍별 수요가 주어져 있을 때, 각 링크를 통과하는 수요의 합 중에서 최대값을 최소화 할 수 있도록, 각 수요쌍별로 링형망의 양쪽방향으로 얼마 만큼의 수요를 전달할 것인 지를 결정하는 문제이다. 단, 수요를 전달할 때는, 그 양이 정수값이어야 한다. 본 연구에서는 이 문제에 대한 하나의 정수계획모형을 제시하고, 이 모형의 선형계획완화문제의 최적목적함수값과 정수최적해의 목적함수값의 절대적인 차이가 1 이하라는 것을 보였다. 또한, 선형계획완화문제를 강화할 수 있는 유효부등식을 제시하고, 이를 첨가하여 강화된 선형계획완화문제의 해결을 통해 정수최적해를 구할 수 있음을 증명하였다.
마지막으로, 파장분할다중화기술을 이용한 전광통신망 설계를 위한 경로설정 및 파장할당문제를 연구하였다. 본 연구에서는 이 문제에 대해 주문제와 부문제로 분해되는 정수계획모형을 제시하고 열생성기법과 분지-한계법을 이용한 해법을 제시하였다. 제시된 해법은 최적해를 보장해 주지 못하지만, 전산실험을 수행한 결과, 최적해에 매우 근사한 해를 준다는 사실을 알 수 있었다.
