Optimization Online


Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs

Luis Gouveia(legouveia***at***fc.ul.pt)
Luidi Simonetti(luidi***at***cos.ufrj.br)
Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: 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 relaxation) 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 proposed 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.

Keywords: Network Design, Integer programming

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Report RPEP Universidade Federal Fluminense Vol. 8 no. 7

Download: [PDF]

Entry Submitted: 06/10/2008
Entry Accepted: 06/20/2008
Entry Last Modified: 06/10/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society