A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem

We present a new Lagrangean relaxation for the hop-constrained minimum spanning tree problem (HMST). The HMST is NP-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 (see Gouveia, L., 1998. Using variable redefinition for computing lower hounds for minimum spanning and Steiner trees with hop constraints. INFORMS Journal on Computing 10, 180-188) 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 how 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. (C) 2001 Elsevier Science B.V. All rights reserved.