A Simulated Annealing algorithm using the Node-depth Phylogenetic structure for the Degree-Constrained Minimum Spanning Tree problem
DOI:
https://doi.org/10.19153/cleiej.29.1.9Keywords:
Degree-constrained minimum spanning tree problem, Simulated Annealing, Node-depth Phylogenetic-based Encoding, Hybrid Genetic Algorithm, CLONALGAbstract
The degree-constrained minimum spanning tree problem (DCMST) is an NP-hard optimization problem defined on connected weighted graphs. It consists of computing a minimum-cost spanning tree of the graph whose nodes have degrees smaller or equal to a predefined constant D. This paper proposes a new heuristic algorithm for solving DCMST, namely the Node-depth Phylogenetic-based Simulated Annealing heuristic (NPE-SA). The proposed algorithm implements the classic Simulated Annealing (SA) metaheuristic using the Node-depth Phylogenetic-based Encoding (NPE), a powerful data structure for indirectly representing spanning trees. Computational experiments performed on two sets of classic instances from the literature demonstrate that NPE-SA outperforms the best metaheuristic from the literature when solving the proposed DCMST instances. Furthermore, it outperforms the Node-depth Phylogenetic-based CLONALG heuristic, another heuristic that implements the NPE data structure.
References
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Minimum spanning trees,” in Introduction
to Algorithms, 4th ed. MIT Press Cambridge, 2022, pp. 585–603.
A. M. de Almeida, P. Martins, and M. C. de Souza, “Min-degree constrained minimum spanning
tree problem: complexity, properties, and formulations,” International Transactions in Operational
Research, vol. 19, no. 3, pp. 323–352, 2012.
H. Akcan, “On the complexity of energy efficient pairwise calibration in embedded sensors,” Applied
Soft Computing, vol. 13, no. 4, pp. 1766 – 1773, 2013.
N. Deo and P. Micikevicius, “A heuristic for a leaf constrained minimum spanning tree problem,” in
Congressus Numerantium. Utilitas Mathematica, 1999, pp. 61–72.
L. Gouveia, A. Paias, and D. Sharma, “Modeling and solving the rooted distance-constrained minimum
spanning tree problem,” Computers & Operations Research, vol. 35, no. 2, pp. 600–613, 2008.
T. F. Noronha, C. C. Ribeiro, and A. C. Santos, “Solving diameter-constrained minimum spanning tree
problems by constraint programming,” International Transactions in Operational Research, vol. 17,
no. 5, pp. 653–665, 2010.
I. A. Carvalho and M. A. Ribeiro, “An exact approach for the minimum-cost bounded-error calibration
tree problem,” Annals of Operations Research, vol. 287, no. 1, pp. 109–126, 2020.
A. E. Ezugwu, A. K. Shukla, R. Nath, A. A. Akinyelu, J. O. Agushaka, H. Chiroma, and P. K. Muhuri,
“Metaheuristics: a comprehensive overview and classification along with bibliometric analysis,” Artificial
Intelligence Review, vol. 54, pp. 4237–4316, 2021.
M. R. Garey and D. S. Johnson, Computers and Intractability. Freeman San Francisco, 1979, vol. 174.
M. Savelsbergh and T. Volgenant, “Edge exchanges in the degree-constrained minimum spanning tree
problem,” Computers & Operations Research, vol. 12, no. 4, pp. 341–348, 1985.
K. Singh and S. Sundar, “A hybrid genetic algorithm for the degree-constrained minimum spanning
tree problem,” Soft Computing, vol. 24, no. 3, pp. 2169–2186, 2020.
A. B. Kahng and G. Robins, On optimal interconnections for VLSI. Springer Science & Business
Media, 1994, vol. 301, ch. 2, pp. 16–63.
R. Ravi, M. V. Marathe, S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III, “Approximation algorithms
for degree-constrained minimum-cost network-design problems,” Algorithmica, vol. 31, pp. 58–78, 2001.
S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol.
, no. 4598, pp. 671–680, 1983.
T. W. de Lima, A. C. B. Delbem, A. da Silva Soares, F. M. Federson, J. B. A. L. Junior, and J. V. Baalen,
“Node-depth phylogenetic-based encoding, a spanning-tree representation for evolutionary algorithms.
part i: Proposal and properties analysis,” Swarm and Evolutionary Computation, vol. 31, pp. 1–10,
I. A. Carvalho and M. A. Ribeiro, “A node-depth phylogenetic-based artificial immune system for
multi-objective network design problems,” Swarm and Evolutionary Computation, vol. 50, p. 100491,
S. C. Narula and C. A. Ho, “Degree-constrained minimum spanning tree,” Computers & Operations
Research, vol. 7, no. 4, pp. 239–249, 1980.
B. Boldon, N. Deo, and N. Kumar, “Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an simd parallel machine,” Parallel Computing, vol. 22, no. 3, pp. 369–382,
L. Caccetta and S. P. Hill, “A branch and cut method for the degree-constrained minimum spanning
tree problem,” Networks: An International Journal, vol. 37, no. 2, pp. 74–83, 2001.
L. H. Bicalho, A. S. Da Cunha, and A. Lucena, “Branch-and-cut-and-price algorithms for the degree
constrained minimum spanning tree problem,” Computational Optimization and Applications, vol. 63,
pp. 755–792, 2016.
G. Zhou and M. Gen, “A note on genetic algorithms for degree-constrained spanning tree problems,”
Networks: an International Journal, vol. 30, no. 2, pp. 91–95, 1997.
J. Knowles and D. Corne, “A new evolutionary approach to the degree-constrained minimum spanning
tree problem,” IEEE Transactions on Evolutionary computation, vol. 4, no. 2, pp. 125–134, 2000.
G. R. Raidl and B. A. Julstrom, “A weighted coding in a genetic algorithm for the degree-constrained
minimum spanning tree problem,” in Proceedings of the 2000 ACM symposium on Applied computingVolume 1, 2000, pp. 440–445.
——, “Edge sets: an effective evolutionary coding of spanning trees,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 3, pp. 225 – 239, 6 2003.
F. Rothlauf and D. Goldberg, “Tree network design with genetic algorithms–an investigation in the
locality of the Pruefernumber encoding,” in Late Breaking Papers at the Genetic and Evolutionary
Computation Conference, 1999, pp. 238 – 244.
M. Krishnamoorthy, A. T. Ernst, and Y. M. Sharaiha, “Comparison of algorithms for the degree constrained minimum spanning tree,” Journal of Heuristics, vol. 7, no. 6, pp. 587 – 611, 11 2001.
M. N. Doan, “An effective ant-based algorithm for the degree-constrained minimum spanning tree
problem,” in 2007 IEEE Congress on Evolutionary Computation. IEEE, 2007, pp. 485–491.
Y.-T. Bau, C. K. Ho, and H. T. Ewe, “Ant colony optimization approaches to the degree-constrained
minimum spanning tree problem,” Journal of Information Science and Engineering, vol. 24, no. 4, pp.
–1094, 2008.
T. N. Bui, X. Deng, and C. M. Zrncic, “An improved ant-based algorithm for the degree-constrained
minimum spanning tree problem,” IEEE Transactions on evolutionary Computation, vol. 16, no. 2, pp.
–278, 2012.
H. T. T. Binh and T. B. Nguyen, “New particle swarm optimization algorithm for solving degree
constrained minimum spanning tree problem,” in PRICAI 2008: Trends in Artificial Intelligence, T.-B.
Ho and Z.-H. Zhou, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 1077–1085.
A. T. Ernst, “A hybrid lagrangian particle swarm optimization algorithm for the degree-constrained
minimum spanning tree problem,” in IEEE Congress on Evolutionary Computation. IEEE, 2010, pp.
–8.
C. C. Ribeiro and M. C. Souza, “Variable neighborhood search for the degree-constrained minimum
spanning tree problem,” Discrete Applied Mathematics, vol. 118, no. 1-2, pp. 43–54, 2002.
W. Wamiliana, “Solving the degree constrained minimum spanning tree problem using tabu and modified penalty search methods,” Jurnal Teknik Industri: Jurnal Keilmuan dan Aplikasi Teknik Industri,
vol. 6, no. 1, pp. 1–9, 2004.
M. Zahrani, M. J. Loomes, J. Malcolm, and A. A. Albrecht, “A local search heuristic for bounded-degree
minimum spanning trees,” Engineering Optimization, vol. 40, no. 12, pp. 1115–1135, 2008.
P. Martins and M. C. de Souza, “Vns and second order heuristics for the min-degree constrained
minimum spanning tree problem,” Computers & Operations Research, vol. 36, no. 11, pp. 2969–2982,
A. M. de Almeida, P. Martins, and M. C. Souza, “md-mst is np-hard for d ¿= 3,” Electronic Notes in
Discrete Mathematics, vol. 36, pp. 9–15, 2010.
S. Ghoshal and S. Sundar, “Two approaches for the min-degree constrained minimum spanning tree
problem,” Applied Soft Computing, vol. 111, p. 107715, 2021.
A. S. da Cunha, L. Simonetti, and A. Lucena, “A strong symmetric formulation for the min-degree
constrained minimum spanning tree problem,” Electronic Notes in Discrete Mathematics, vol. 52, pp.
–244, 2016.
J. D. Knowles and D. W. Corne, “Benchmark problem generators and results for the multiobjective
degree-constrained minimum spanning tree problem,” in Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO-2001), 2001, pp. 424–431.
E. F. G. Goldbarg, G. R. de Souza, and M. C. Goldbarg, “Particle swarm optimization for the biobjective degree constrained minimum spanning tree,” in 2006 IEEE International Conference on Evolutionary Computation. IEEE, 2006, pp. 420–427.
A. Ghosh, O. D. Incel, V. A. Kumar, and B. Krishnamachari, “Multichannel scheduling and spanning ¨
trees: Throughput–delay tradeoff for fast data collection in sensor networks,” IEEE/ACM Transactions
on Networking, vol. 19, no. 6, pp. 1731–1744, 2011.
M. K. An and H. Cho, “Construction of bounded-degree minimum-radius spanning trees for wsns,” in
IEEE 15th Annual Computing and Communication Workshop and Conference (CCWC). IEEE,
, pp. 95–102.
T. J. Kumar and P. Singamsetty, “An exact algorithm for multi-constrained minimum spanning tree
problem,” International Journal of Mathematics in Operational Research, vol. 12, no. 3, pp. 317–330,
P. Adasme and A. Dehghan Firoozabadi, “Degree-constrained k-minimum spanning tree problem,”
Complexity, vol. 2020, no. 1, p. 7628105, 2020.
D. Delahaye, S. Chaimatanan, and M. Mongeau, “Simulated annealing: From basics to applications,”
in Handbook of Metaheuristics, M. Gendreau and J.-Y. Potvin, Eds. Cham: Springer International
Publishing, 2019, pp. 1–35. [Online]. Available: https://doi.org/10.1007/978-3-319-91086-4 1
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state
calculations by fast computing machines,” The journal of chemical physics, vol. 21, no. 6, pp. 1087–1092,
A. C. B. Delbem, A. de Carvalho, C. A. Policastro, A. K. O. Pinto, K. Honda, and A. C. Garcia, “Nodedepth encoding for evolutionary algorithms applied to network design,” in Genetic and Evolutionary
Computation – GECCO 2004, K. Deb, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp.
– 687.
A. Smith and D. Coit, “Constraint-handling techniques,” in Handbook of Evolutionary Computation,
T. Baeck, D. B. Fogel, and Z. Michalewicz, Eds. Boca Raton: CRC Press, 1997, pp. 344–377.
E. Mezura-Montes and C. A. C. Coello, “Constraint-handling in nature-inspired numerical optimization:
past, present and future,” Swarm and Evolutionary Computation, vol. 1, no. 4, pp. 173–194, 2011.
L. N. de Castro and F. J. V. Zuben, “Learning and optimization using the clonal selection principle,”
IEEE Transactions on Evolutionary Computation, vol. 6, no. 3, pp. 239 – 251, 6 2002.
M. Matsumoto and T. Nishimura, “Mersenne twister: A 623-dimensionally equidistributed uniform
pseudo-random number generator,” ACM Transactions on Modeling and Computer Simulation, vol. 8,
no. 1, pp. 3 – 30, 1 1998.
T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama, “Optuna: A next-generation hyperparameter optimization framework,” in Proceedings of the 25th ACM SIGKDD international conference on
knowledge discovery & data mining, 2019, pp. 2623–2631.
J. Derrac, S. Garc´?a, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric
statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Swarm
and Evolutionary Computation, vol. 1, no. 1, pp. 3–18, 2011.
I. A. Carvalho, “On the statistical evaluation of algorithmic’s computational experimentation wit
infeasible solutions,” Information Processing Letters, vol. 143, pp. 24–27, 2019.
V. Maniezzo, T. St¨utzle, and S. Voß, Matheuristics. Springer, 2021.
I. A. Carvalho and A. A. Coco, “Data, instance sets, and instances generator for the hop-constrained
minimum spanning tree problem, the delay-constrained minimum spanning tree problem, and their
bi-objective variants,” Data in Brief, vol. 50, p. 109553, 2023.
E. Osaba, E. Villar-Rodriguez, and S. V. Romero, “Benchmark dataset and instance generator for
real-world three-dimensional bin packing problems,” Data in Brief, vol. 49, p. 109309, 2023.
E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, “New benchmark instances
for the capacitated vehicle routing problem,” European Journal of Operational Research, vol. 257, no. 3,
pp. 845–858, 2017.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Iago Augusto Carvalho, José Flavio Lopes
This work is licensed under a Creative Commons Attribution 4.0 International License.
CLEIej is supported by its home institution, CLEI, and by the contribution of the Latin American and international researchers community, and it does not apply any author charges whatsoever for submitting and publishing. Since its creation in 1998, all contents are made publicly accesibly. The current license being applied is a (CC)-BY license (effective October 2015; between 2011 and 2015 a (CC)-BY-NC license was used).
