Authors
Thiago Ferreira Noronha, Celso Carneiro Ribeiro, Andréa Cynthia Santos,
Title
Solving diameter-constrained minimum spanning tree problems by constraint programming
In
International Transactions in Operational Research
Volume
17
Issue
5
Pages
653–665
Publisher
Wiley
Year
2010
Publisher's URL
http://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2010.00780.x/abstract;jsessionid=FA4EF9E44A35C6A2FDED11DD045B692A.f01t03
Indexed by
Abstract
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.
Affiliations
Offprint