Designing a minimal spanning tree network subject to a budget constraint

The problem of determining a minimal spanning tree, subject to side constraints, arises frequently in the design of computer communication networks and pipeline systems. In this paper, a specific case of the general problem, with only one side constraint of the knapsack type is considered. For its solution, a new Lagrangean relaxation, based on a reformulation of the problem through the utilization of duplication of variables, is developed. Theoretical and computational results, indicating the superiority of the new approach, over the straightforward Lagrangean relaxation, are presented. Finally, the possibility of adopting the approach for the solution of more general problems is demonstrated.