The use of partitioning strategies in local access telecommunication network problems and other applications

Abstract

Telecommunications networks can usually hierarchically be divided into three parts. The local access telecommunications network (LATN) connects individual subscribers to the network and makes a significant contribution to the total telecommunications network cost. The Tree Knapsack Problem (TKP) and Extended Tree Knapsack Problems (ETKP) can be used to model some aspects of the LATN design problem. Efficient solution methods for these models can improve planning of LATN's as it may be necessary to solve many such problems for different scenarios. The TKP and ETKP models are investigated and solution methods found in the literature are discussed. New exact solution methods for the TKP and ETKP models are proposed. These solution methods are based on enhanced modeling and partitioning strategies and use standard off the shelf software. The idea is to produce a solution strategy that utilises the strengths of modern optimisation software and hardware platforms to solve problems of realistic size. The algorithms were evaluated by using planned empirical methods. Results of the experimental work and comparisons are presented. The suggested partitioning and enhanced modeling approaches performed well when compared to other solution approaches, in the sense that more stable solution times were observed as well as better capabilities with larger problem instances. It appears to be feasible to use enhanced modeling and partitioning to solve TKP and ETKP problems.