Список выпусков > Серия «Математика». 2011. Том 2
Построение минимального остова с ограниченной пропускной способностью методом имитации отжига
В статье рассматривается задача о минимальном остове с ограниченной пропускной способностью (CMST), относящаяся к классу NP-трудных. Разработан модифицированный метод имитации отжига, позволяющий получать лучшие решения CMST, чем классическая версия метода. Приводятся результаты вычислительного эксперимента.
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