We consider several designing and routing problems for capacitated telecommunication networks. We present formulations for the problems and algorithms for them which are based on the integer programming approaches.
First, we consider the variable sized bin packing problem which arises in Asynchronous Transfer Mode (ATM) Virtual Path (VP)-based leased line networks.
The objective of the problem is to minimize the total cost of used bins when the cost of unit size of each bin does not increase as the bin size increases. Two greedy algorithms are described, and analyzed in three special cases: a) the sizes of items and bins are divisible, respectively, b) only the sizes of bins are divisible, and c) the sizes of bins are not divisible. Here, we say that a list of numbers $a_1, a_2, …, a_m$ are divisible when $a_j$ exactly divides $a_{j-1}$, for each 1 ＜ j ≤ m. In the case of a), the algorithms give optimal solutions, and in the case of b), each algorithm gives a solution whose value is less than $\frac{11}{9}C(B^*) +4\frac{11}{9}$, where $C(B^*)$ is the optimal value. In the case of c), each algorithm gives a solution whose value is less than $\frac{3}{2}C(B^*) +1$.
Second, we consider the problem of designing an ATM VP-based leased line backbone network. Given point-to-point communication demands having predefined sizes in a network, the problem is to find configurations of demand routes and link facilities installed on each edge satisfying all demands at minimum cost under some constraints. One of the most important constraints is that a single demand cannot be split over multiple link facilities. This is a sort of bin packing constraint. We propose an integer programming formulation of the problem and an algorithm to solve it. An efficient column generation technique to solve the linear programming relaxation is proposed, and a valid inequality is used to strengthen the integer programming formulation. The algorithm incorporates the column generation technique and the cutting plane approach into a branch-and-bound scheme. We test the proposed algorithm on some real problems. The results show that the algorithm can be used to solve the problems within reasonably small time limits.
Third, to generate a multicast routing tree guaranteeing the required quality of service (QoS), we consider the hop constrained Steiner tree problem and propose a new mathematical formulation for it, which contains fewer constraints than a previously known formulation. An efficient procedure is also proposed to solve the problem. Preliminary tests show that the procedure reduces the computing time significantly.
Finally, we consider the hop-constrained multicast route packing problem with bandwidth reservation. Given a set of multicast sessions, each of which has a hop limit constraint and a required bandwidth, the problem is to determine a set of multicast routing trees in an arc-capacitated network to minimize cost. We propose an integer programming formulation of the problem and an algorithm to solve it. An efficient column generation technique to solve the linear programming relaxation is proposed, and a modified cover inequality is used to strengthen the integer programming formulation. The algorithm incorporates the column generation technique and the cutting plane approach into a branch-and-bound scheme. We test the proposed algorithm on some randomly generated problems. The results show that the algorithm can be used to solve the problems within reasonably small time limits.
통신망 설계 및 운용을 위해서 일반적으로 통신장비 설치 위치결정, 설치 장비의 용량결정, 장비들 사이의 연결을 위한 전송 용량결정, 및 정보 전송 경로결정이 동시에 이루어져야 한다. 그러나, 이러한 세부 사항들을 동시에 모두 결정하는 문제는 상당히 복잡하기 때문에 각 부분으로 나누어서 문제를 해결한다. 특히, `장비 위치결정', `전송 용량결정', 그리고 `경로결정' 문제로 일반적으로 분할되어 독립적으로 해결된다. 최근에는 보다 효율적인 망 설치 및 관리를 위하여 `전송 용량결정'과 `경로결정'을 동시에 수행하는 방법들이 연구되고 있다. 본 연구에서, 이런 이유로 전송 경로가 결정된 경우와 그렇지 않은 경우 각각에 대한 `전송 용량결정' 문제에 대해서 연구하였다. 또한, 이미 전송 장치들이 설치된 통신망에서 전송 용량의 제약을 고려하여 미래에 폭발적으로 증가할 것이라고 예측되는 인터넷 방송, 화상 회의와 같은 대용량 멀티캐스트 정보의 전송 경로결정 문제에 대해서도 연구하였다.
첫째, 전송 경로가 결정된 상태에서 전송 용량을 결정하는 문제에 대해서 연구하였다. 우리는 이 문제를 `다용량 bin packing 문제(the variable sized bin packing problem)'로 모형화 하였으며, 두 가지 해법을 제시하였다. 이 해법들은 전송장비의 용량이 155.52Mbps(STM-1), 622.08Mbps(STM-2), 2.488Gbps(STM-16)처럼 155.52Mbps를 기준으로 배수로 증가하고, 대상 서비스들의 요구 대역폭도 배수로 증가하는 경우에 대해서 항상 최적해를 제공한다.
둘째, 전송 용량 및 경로를 동시에 결정하는 문제에 대해서 연구하였다. 이 문제에 대해서 정수계획모형과 해법을 제시하였다. 정수계획모형에는 전송장비의 용량과 서비스의 요구 대역폭이 각각 배수로 증가하는 경우에 대해서 전송장비단위별 경로 결정 없이 전송경로를 결정할 수 있도록 하는 제약식이 개발되어 사용되었다. 선형완화모형을 효과적으로 풀기위해서 열생성기법을 사용하였으며, 모형을 강화하기 위해서 유효부등식이 사용되었다. 실험을 통해서 제시된 알고리즘이 비교적 짧은 시간 안에 문제를 해결한다는 것을 보였다.
셋째, 전송품질(QoS)를 보장하는 멀티캐스트 정보의 전송경로를 결정하는 문제에 대해서 연구하였다. 이 문제를 hop제약을 갖는 Steiner 나무 문제로 모형화 하였으며, 이에 대한 효율적인 정수모형과 해법을 제시하였다. 제시된 정수모형은 기존 모형과 동일한 선형완화 한계하한을 제공하지만 상당히 적은 수의 열과 행을 포함하기 때문에 계산시간을 상당히 감소시킨다.
마지막으로, 용량제약이 있는 통신망에서 다수의 멀티캐스트 정보의 전송경로를 동시에 결정하는 문제에 대해서 연구하였다. 이 문제에 대해서 정수계획모형을 제시하였으며, 이를 위한 해법으로 열생성기법과 유효부등식을 포함하는 분지한계법을 제시하였다. 선형완화식을 효율적으로 풀기위해서 열생성기법을 사용하였으며, 선형완화식의 하한을 증가시키기 위해서 변형된 cover 부등식을 사용하었다. 실험을 통해서 제시된 해법이 문제를 빠른 시간에 해결하는 것을 확인하였다. 특히, 선형완화식의 하한을 구한 직후 단순한 분지한계법을 사용하여 얻은 중간해(incumbent solution)가 일반적으로 최적해를 제공하였다.
