Solving the Extended Tree Knapsack Problem with xed cost ow expansion functions

Parts of the Local Access Telecommunication Network planning problem may be modelled as an Extended Tree Knapsack Problem. The Local Access Telecommunication Network can contribute up to 60% of the total network costs. This paper presents partitioning algorithms that use standard o-the-shelf software coupled with enhanced modelling. Enhancements to the algorithms and empirical results for both the Tree Knapsack Problem and Extended Tree Knapsack Problem are presented. Key words: Tree algorithms, telecommunications, location problems, capacity expansion.