Path packing problems in a telecommunication network

Abstract

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.