We present a new Lagrangean relaxation for the hop-constrained minimum spanning tree problem (HMST). The HMST is N P-hard and models the design of centralized telecommunication networks with quality of service constraints. The linear programming (LP) relaxation of a hop-indexed flow-based model recently presented in the literature (by Gouveia) produces very tight bounds but has the disadvantage of being very time consuming, especially for dense graphs. In this paper, we present a new Lagrangean relaxation which is derived from the hop-indexed flow based formulation. Our computational results indicate that the lower bounds given by the new relaxation dominate the lower bounds given by previous Lagrangean relaxations. Our results also show that for dense graphs the new Lagrangean relaxation proves to be a reasonable alternative to solving the LP relaxation of the hop-indexed model.
