Keywords
graph coloring
heuristics
combinatorial optimization
discrete optimization
Búsqueda dispersa
coloración de gráficas
heurísticas
optimización combinatoria
optimización discreta
How to Cite
Abstract
Let G and G be two complementary graphs. Given a penalty function defined over the edges of G, it is said that the rigidity of a k-coloring of G is the summation ofthe penalties of the edges of G that join vertices whose endpoint are equally colored. Based on this previous definition, the Robust Coloring Problem is set when searching the valid k-coloring of minimum rigidity. Yáñez and Ramírez proved that this is an NP-hard problem. In this work we present an evolutive algorithm based in the scatter search technique, which obtains optimal solutions for those instances for which an optimal solution is known, and obtains the best known solutions compared to other heuristics, such as: simulated annealing, tabu search and partial enumeration.
References
Glover, F. (1998) “A template for scatter search and path relinking”, in: J.K. Hao, E. Lutton, E. Ronald, M. Shoenauer & D. Snyers (Eds.) Artificial Evolution, Lecture Notes in Computer Science, 1363, Springer: 13–54.
Glover, F.; Laguna, M.; Martí, R., (2004) “Scatter search and path relinking: foundations and advanced designs”, in: G. Onwubolu (Ed.) New Optimization Techniques in Enginneering, Springer Verlag.
Glover, F.; Laguna, M.; Martí, R. (2004) “New ideas and applications of scatter search and path relinking”, in: G. Onwubolu (Ed.) New Optimization Techniques in Enginneering, Springer Verlag.
Laguna, M.; Armentano, V. (2004) “Lessons from applying and experimenting with scatter search”, in: C. Rego & B. Alidaee (Eds.) Adaptive Memory and Evolution: Tabu Search and Scatter Search,
Ramı́rez Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis de Doctorado, Universidad Complutense de Madrid, Madrid, España.
Ramı́rez Rodríguez J.; Gutiérrez Andrade, M.A.; López Bracho, R.; Yáñez Gestoso, J., (2004) “Heuristics for the robust coloring problem”, Preprint, Universidad Autónoma Metropolitana, México.
Yáñez, J., Ramı́rez, J. (2003) “The robust coloring problem”, European Journal of Operational Research, 148(3): 546–558.}