We consider several clustering and routing problems for the design of capacitated telecommunication networks. We present integer programming formulations of the problems and algorithms for them.
First, we consider the switching node location problem for the design of ATM (Asynchronous Transfer Mode) networks. In this problem, there are two kinds of facilities, called hub facilities and remote facilities, with different capacities and installation costs. We are given a set of customers with demand requirements, a set of candidate sites for facility installation, and connection costs between facilities. We need to determine the locations to place facilities, the number of facilities for each selected location, the set of customers who are connected to each installed hub via installed remote facilities. The objective is to minimize the total cost while satisfying demand requirements of each customer. We formulate this problem as a general integer programming problem and solve it to optimality. In this study, we present a preprocessing procedure to tighten the formulation and develop a branch-and-price algorithm. In the algorithm, we consider the integer knapsack problem to solve the column generation problem. Computational experiments show that the algorithm gives optimal solutions in a reasonable time.
Second, we consider the clustering problem for the design of ATM VP (Virtual Path)-based leased line networks. In this problem, we are given a network, which is composed of a set of access nodes with demand requirements and conduits connecting the access nodes, a set of candidate edge nodes chosen from the access nodes, and a set of facilities with different capacities and installation costs. We need to determine a partitioning of the whole network into clusters, and the facility types to be installed at the edge nodes to accommodate the demand requirements of the access nodes with minimum cost. Each cluster contains one edge node and a subset of access nodes, and should satisfy the simple connectivity requirement in the physical network. We formulate this problem as an integer programming problem and solve it to optimality. To solve this problem, we identify some cutting planes and incorporate them in a branch-and-cut algorithm. Computational results show that the algorithm gives optimal solutions in a reasonable time.
Third, we consider the constraint based explicit routing problem which arises in MPLS (Multi-Protocol Label Switching) based IP Networks. In this problem, we are given a set of traffic demands and a network with different link capacities. We then consider how to set up explicit routes to meet bandwidth demands between the edge nodes of the network and at the same time to optimize the network performance. We model this problem as an integer programming problem. The objective is to minimize the maximum link load ratio of the network. We decompose the problem and propose an efficient column generation algorithm. To strengthen the formulation of the problem, we also consider some valid inequalities in the preprocessing. We then incorporate the column generation algorithm with a variable fixing scheme. Computational results show that the algorithm gives high quality solutions in a short execution time.
Finally, we consider two types of path selection problems for arc capacitated networks. Given an arc capacitated network and a set of commodities, one problem is to find a subset of commodities to be routed and an assignment of them to the paths so that profit is maximized. The other problem is to route all given commodities in the network so that cost is minimized. Bifurcation of flow is not allowed in both cases. We formulate the problems as integer programming models and solve them. Column generation technique to solve the linear programming relaxation is proposed with two types of columns. To obtain an optimum integer solution for the problems, we propose a branching strategy in the branch-and-price scheme. Computational experiments show that the algorithm gives optimal solutions within reasonably small computing time.
본 논문에서는 통신망 설계를 위한 클러스터링 및 경로설정 문제들에 대한 정수계획모형과 정수계획기법에 기반한 해법을 제시하고 있다.
첫째, 광대역 통신망 설계를 위한 교환기 위치 설정 문제를 연구하였다. 본 문제에서 고려하는 교환기는 허브 교환기와 하부 교환기 두 종류이다. 이들은 종류에 따라 각기 다른 이산적인 용량과 비용구조를 가지며, 모든 수요는 하부 교환기를 통하여 허브 교환기로 전송이 이루어진다. 본 문제는 모든 수요를 만족시키기 위한 교환국 후보 위치별 교환기 대수 및 이들간의 연결을 최소의 비용으로 구성하는 것이다. 본 연구에서는 문제의 복잡도를 고려하여 이 문제를 주문제와 부문제로 나누어 모형화하고, 이 문제에 대한 선형계획완화문제를 강화할 수 있는 유효부등식을 제안하였다. 주문제의 열을 생성하는 부문제는 상한이 있는 정수배낭문제로서 본 연구에서는 이 문제를 해결하기 이하여 동적 계획법을 사용하였다. 이러한 결과를 종합하여, 본 문제의 최적해를 구할 수 있는 열생성 기법과 분지-평가법을 이용한 해법을 제시하였다. 실제 크기의 데이터에 대한 본 연구의 해법을 실험한 결과 타당한 시간 내에 최적해를 구할 수 있었다. 둘째, 광대역 통신망 설계를 위한 가입자 수용계획 문제를 연구하였다. 본 문제는 가입자들이 속한 교환국들로 이루어진 물리적인 관로망과 이들의 수요를 수용하기 위한 허브 후보지들이 주어졌을 때, 수요전송비용과 교환비용을 최소화하도록 교환국들을 허브 후보지 중 하나에 할당하는 문제이다. 본 연구에서는 이 문제에 대한 정수계획모형을 제시하고, 선형계획완화문제를 강화할 수 있는 전처리 과정 및 유효부등식을 제안하였다. 이러한 결과를 토대로 본 문제의 최적해를 구할 수 있는 분지-절단 해법을 제시하였다. 전산실험을 수행한 결과, 본 연구에서 제안한 전처리 과정 및 유효부등식 생성 방안은 해법의 성능을 상당히 개선시킨다는 것을 알 수 있었다.
셋째, 가상사설망을 비릇한 인터넷 백본망에서 전송품질(QoS)을 만족시키기 위한 명시적 경로설정문제를 연구하였다. 본 문제는 라우터들로 이루어진 하나의 관로망과, 소요노드쌍들의 집합 및 각 수요쌍별 수요가 주어져 있을 때, 전송품질을 반영하는 홉 제약을 고려하면서 각 링크게 가해지는 링크 하중비(링크 용량대비 링크를 지나는 수요의 합)의 최대값을 최소화 할 수 있도록, 각 수요쌍별로 수요를 전달 할 수 있는 명시적 경로를 설정하는 문제이다. 본 연구에서는 이 문제에 대해 주문제와 부문제로 분해되는 정수계획모형을 제시하고, 열생성 기법과 분지-한계법을 이용한 해법을 제시하였다. 제시된 해법은 최적해를 보장해 주지 못하지만, 전산실험을 수행한 결과, 최적해에 매우 근사한 해를 준다는 사실을 알 수 있었다.
마지막으로, 링크 용량제약이 있는 통신망에서 수요쌍들간의 수요를 만족시키기 위한 두 종류의 경로설정문제를 연구하였다. 한 문제는 수요쌍들 중 일부만 경로를 설정해야 할 경우 발생 수익의 합을 최대화하는 것이며, 나머지 한 문제는 모든 수요를 만족시켜야 할 경우 결로설정 비용의 합을 최소화하는 것이다. 본 연구에서는 두 문제에 대한 정수계획모형을 제시하고, 열생성 기법과 분지-평가법을 이용한 해법을 제시하였다. 본 연구에서는 두 종류의 열생성 문제를 고려한 선형완화기법과 각 문제의 정수 최적해를 얻기 위한 분지법에 대하여 다루었다. 전산실험을 수행한 결과, 최적해를 빠른 시간안에 구할 수 있다는 것을 알 수 있었다.
