journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>В статье рассматривается задача о минимальном остове с ограниченной пропускной способностью (CMST), относящаяся к классу NP-трудных. Разработан модифицированный метод имитации отжига, позволяющий получать лучшие решения CMST, чем классическая версия метода. Приводятся результаты вычислительного эксперимента.</p>

Ключевые слова RU

Литература RU
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

Название EN

Авторы EN

Аннотация EN
<p>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.</p>

Ключевые слова EN

Литература EN