Geodesic
Building a capacitated minimum spanning tree using simulated annealing
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 2, pp. 114-123 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: capacitated minimum spanning tree; simulated annealing; metaheuristic; neighborhood. 
@article{IIGUM_2011_4_2_a8,
     author = {A. Ipatov},
     title = {Building a capacitated minimum spanning tree using simulated annealing},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {114--123},
     year = {2011},
     volume = {4},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a8/}
}
TY  - JOUR
AU  - A. Ipatov
TI  - Building a capacitated minimum spanning tree using simulated annealing
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 114
EP  - 123
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a8/
LA  - ru
ID  - IIGUM_2011_4_2_a8
ER  - 
%0 Journal Article
%A A. Ipatov
%T Building a capacitated minimum spanning tree using simulated annealing
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 114-123
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a8/
%G ru
%F IIGUM_2011_4_2_a8
A. Ipatov. Building a capacitated minimum spanning tree using simulated annealing. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 2, pp. 114-123. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a8/

[1] A. V. Ipatov, “Modifitsirovannyi metod imitatsii otzhiga v zadache CMST”, Inform. byul. Assotsiatsii mat. programmirovaniya, 12, UrO RAN, Ekaterinburg, 2011, 182–183

[2] A. V. Ipatov, “Ob odnom metode postroeniya okrestnosti v zadache CMST”, Sovremennye problemy matematiki, Tez. 42-i vseros. molodezh. shk.-konf., IMM UrO RAN, Ekaterinburg, 2011, 161–163

[3] R. K. Ahuja, J. B. Orlin, D. Sharma, “Multi-exchange neighborhood search algorithms for the capacitated minimum spanning tree problem”, Mathematical Programming, 91 (2001), 71–97 | MR | Zbl

[4] A. Amberg, W. Domschke, S. Voss, “Capacitated minimum spanning trees: Algorithms using intelligent search”, Combinatorial Optimization: Theory and Practice, v. 1, 1996, 9–39

[5] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to algorithms, second edition, The MIT Press, Cambridge, MA, 2001, 1184 pp. | MR | Zbl

[6] D. Elias, M. Ferguson, “Topological design of multipoint teleprocessing networks”, IEEE Transactions on Communications, 22 (1974), 1753–1762 | DOI

[7] H. Frank, I. T. Frisch, R. Van Slyke, W. S. Chou, “Optimal design of centralized computer networks”, Networks, 1 (1971), 43–57 | DOI | MR | Zbl

[8] C. H. Papadimitriou, “The complexity of the capacitated tree problem”, Networks, 8 (1978), 217–230 | DOI | MR

[9] Y. M. Sharaiha, M. Gendreau, G. Laporte, I. H. Osman, “A tabu search algorithm for the capacitated shortest spanning tree”, Networks, 29 (1997), 161–171 | 3.0.CO;2-F class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] E. Uchoa et al., “Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation”, Mathematical Programming: Series A and B, 112:2 (2007), 443–472 | DOI | MR

[11] S. Voss, “Capacitated minimum spanning trees”, Encyclopedia of optimization, v. 6, eds. C. A. Floudas, P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, 2001, 225–235 | DOI

[12] http://people.brunel.ac.uk/m̃astjjb/jeb/orlib/capmstinfo.html