A Lagrangean Heuristic For The Degree Constrained Minimal Spanning Tree Problem

Abstract

In this paper we present a new heuristic procedure to solve the degree constrained minimal spanning tree problem. This procedure uses Lagrangian relaxation of the integer programming formulation of the problem to get a lower bound for the optimal objective function value. A subgradient optimization method is used to find multipliers that give good lower bounds. A branch exchange procedure is used after each iteration of the subgradient optimization to generate a feasible solution from an infeasible Lagrangean solution. Computational results are given for problems with up to 300 nodes. The heuristic procedure presented here gives optimal solutions in most instances. For problem sets that were not solved optimally, the gap between the lower bound and the feasible solution was less than 10^-2 percent.