A Lagrangean Based Heuristic for the Degree Constrained Capacitated Minimal Spanning Tree Problem

摘要

In this paper we formulate the degree constrained capacitated minimal spanning tree problem as an integer programming problem that leads to a lagrangean relaxation of the problem. A subgradient optimization technique is used on this relaxation to find good lower bounds on the optimal objective function value. A branch exchange procedure is used in every iteration of the subgradient optimization method to generate a feasible solution from each infeasible Lagrangean solution. The best feasible solution is retained when the subgradient optimization mehtod is terminated.