|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|
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.