List of issues > Series «Mathematics». 2011. Vol. 2
Building a capacitated minimum spanning tree using simulated annealing
In this paper we consider capacitated minimum spanning tree problem (CMST) which is NP-hard. We have developed enhanced simulated annealing method, which allows getting better solutions for CMST than the classical one. Computational results on the benchmark instances are reported.
1. Ипатов А. В. Модифицированный метод имитации отжига в задаче CMST / А. В. Ипатов // Информ. бюл. Ассоциации мат. программирования. – Екатеринбург : УрО РАН, 2011. – Вып. 12. – С. 182–183.
2. Ипатов А. В. Об одном методе построения окрестности в задаче CMST / А. В. Ипатов // Современные проблемы математики : тез. 42-й всерос. молодёж. шк.-конф. – Екатеринбург : ИММ УрО РАН, 2011. – С. 161–163.
3. Ahuja R. K. Multi-exchange neighborhood search algorithms for the capacitated minimum spanning tree problem / R. K. Ahuja, J. B. Orlin, D. Sharma // Mathematical Programming. – 2001. – Vol. 91. – P. 71–97.
4. Amberg A. Capacitated minimum spanning trees: Algorithms using intelligent search / A. Amberg, W. Domschke, S. Voss // Combinatorial Optimization: Theory and Practice. – 1996. – Vol. 1. – P. 9–39.
5. Introduction to algorithms, second edition / T. Cormen, C. Leiserson, R. Rivest, C. Stein. – The MIT Press, Cambridge, MA, 2001. – 1184 p.
6. Elias D. Topological design of multipoint teleprocessing networks / D. Elias, M. Ferguson // IEEE Transactions on Communications. – 1974. – Vol. 22. – P. 1753–1762.
7. Optimal design of centralized computer networks / H. Frank, I.T. Frisch, R. Van Slyke, W. S. Chou // Networks. – 1971. – Vol. 1. – P. 43–57.
8. Papadimitriou C. H. The complexity of the capacitated tree problem / C. H. Papadimitriou // Networks. – 1978. – Vol. 8. – P. 217–230.
9. A tabu search algorithm for the capacitated shortest spanning tree / Y. M. Sharaiha, M. Gendreau, G. Laporte, I. H. Osman // Networks. – 1997. – Vol. 29. – P. 161–171.
10. Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation / E. Uchoa [et al.] // Mathematical Programming: Series A and B. – 2007. – Vol. 112, Iss. 2. – P. 443–472.
11. Voss S. Capacitated minimum spanning trees / S. Voss // Encyclopedia of optimization / eds. C. A. Floudas, P. M. Pardalos. – Kluwer Academic Publishers, Doordrecht, 2001. – Vol. 6. – P. 225–235.
12. Capacitated minimal spanning tree [Electronic resource]. – URL: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/capmstinfo.html