Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 19
On formulations and methods for the hop-constrained minimum spanning tree problem
G. Dahl, L. Gouveia, and C. Requejo
Abstract
In this chapter we present a general framework for modeling the hopconstrained minimum spanning tree problem (HMST) which includes formulations already presented in the literature. We present and survey different ways of computing a lower bound on the optimal value. These include, Lagrangian relaxation, column generation and model reformulation. We also give computational results involving instances with 40 and 80 nodes in order to compare some of the ideas discussed in the chapter.
Keywords: Hop-constrained spanning trees, polyhedral characterizations, model reformulation.