Solving diameter constrained minimum spanning tree problems in dense graphs

Andrea Santos (cynthiainf.puc-rio.br)
Abílio Lucena (lucenafacc.ufrj.br)
Celso Ribeiro (celsoinf.puc-rio.br)

Abstract: In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An alternative formulation is also proposed for instances of the problem where the diameter of feasible spanning trees can not exceed given odd numbers. This formulation dominated their counterparts in this study, in terms of the computation time required to obtain proven optimal solutions. First ever computational results are presented here for complete graph instances of the problem. Sparse graph instances as large as those found in the literature were solved to proven optimality for the case where diameters can not exceed given odd numbers. For these applications, the corresponding computation times are competitive with those found in the literature.

Keywords: Spanning tree, diameter-constrained, network design, lifting

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (0-1 Programming )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, February 2004.

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/05/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry