Построение минимального остова с ограниченной пропускной способностью методом имитации отжига
| Авторы: | А. В. Ипатов |
| Аннотация: | В статье рассматривается задача о минимальном остове с ограниченной пропускной способностью (CMST), относящаяся к классу NP-трудных. Разработан модифицированный метод имитации отжига, позволяющий получать лучшие решения CMST, чем классическая версия метода. Приводятся результаты вычислительного эксперимента. |
| Ключевые слова: | минимальный остов, имитация отжига, метаэвристика, окрестность |
| УДК: | 519.854.2 |
| Литература: |
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 |