Solving the Extended Tree Knapsack Problem with fixed cost flow expansion functions

Abstract

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 off-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.