Article ID: | iaor20105933 |
Volume: | 17 |
Issue: | 5 |
Start Page Number: | 653 |
End Page Number: | 665 |
Publication Date: | Sep 2010 |
Journal: | International Transactions in Operational Research |
Authors: | Ribeiro Celso C, Santos Andra C, Noronha Thiago F |
Keywords: | programming: constraints |
The diameter-constrained minimum spanning tree problem consists in finding a minimum spanning tree of a given graph, subject to the constraint that the maximum number of edges between any two vertices in the tree is bounded from above by a given constant. This problem typically models network design applications where all vertices communicate with each other at a minimum cost, subject to a given quality requirement. We propose alternative formulations using constraint programming that circumvent weak lower bounds yielded by most mixed-integer programming formulations. Computational results show that the proposed formulation, combined with an appropriate search procedure, solves larger instances and is faster than other approaches in the literature.