Modeling Hop‐constrained and Diameter‐constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs

The Hop-Constrained Minimum Spanning Tree Problem (HMSTP) is a NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner Tree Problem (STP) in an adequate layered graph. We prove that the directed cut formulation for the STP defined in the layered graph, dominates (in terms of the linear programming relax-ation) the best previously known formulations for the HMSTP. We then show how cuts in the extended layered graph space can be projected into new families of cuts in the original design space. We also adapt the pro-posed approach for the Diameter-Constrained Minimum Spanning Tree Problem (DMSTP). For situations when the diameter is odd we propose a new transformation into a single center problem that is quite effective. Computational results with a branch-and-cut algorithm show that the proposed method is significantly better than previously known methods on both problems