A hybrid algorithm for the robust graph coloring problem

• Autores: Román Anselmo Mora Gutiérrez, Javier Ramirez Rodríguez, Eric Alfredo Rincón García, Antonin Ponsich, Ana Lilia Laureano Cruces
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 23, Nº. 2, 2016, págs. 421-444
• Idioma: inglés
• DOI: 10.15517/rmta.v23i2.25269
• Títulos paralelos:
  • Un algoritmo híbrido para el problema de coloración robusta de gráficas
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este artículo se propone un algoritmo híbrido que combina técnicas de programación matemática (algoritmo de Kruskal y la estrategia de mantener consistencia de arcos para resolver el problema de satisfacción de restricciones) y métodos heurísticos (método de composición musical y DSATUR) para resolver el problema de coloración robusta de gráficas (RGCP). Resultados experimentales muestran que este algorimo da mejores resultados que otros presentados en la literatura.

  • English

    A hybridalgorithm which combines mathematical programming techniques (Kruskal’s algorithm and the strategy of maintaining arc consistency to solve constraint satisfaction problem “CSP”) and heuristic methods (musical composition method and DSATUR) to resolve the robust graph coloring problem (RGCP) is proposed in this paper. Experimental result shows that this algorithm is better than the other algorithms presented on the literature.

• Referencias bibliográficas
  • Archetti, C.; Bianchessi, N.; Hertz, A. (2014) “A branch-and-price algorithm for the robust graph coloring problem”, Discrete Applied Mathematics...
  • Berge, C. (1973) Graphes et Hypergraphes. Dunod, Paris.
  • Birattari, M. (2009) Tuning Metaheuristics: A Machine Learning Perspective. Springer, Berlin.
  • Brailsford, S.C.; Potts, C.N.; Smith, B.M. (1999) “Constraint satisfaction problems: Algorithms and applications”, European Journal of Operational...
  • Brélaz, D. (1979) “New methods to color the vertices of a graph”, Communications of the ACM 22(4): 251–256.
  • Burke, E.; Jackson, K.; Kingston, J H.; Weare, R. (1997) “Automated university timetabling the state of the art”, The Computer Journal 40(9):...
  • Chams, M.; Hertz, A.; de Werra, D. (1987) “Some experiments with simulated annealing for coloring graphs”, European Journal of Operational...
  • Feo, T.A.; Resende, M.G.C. (1995) “Greedy randomized adaptive search procedures”, J. of Global Optimization 6(2): 109–133.
  • Glover, F. (1986) “Future paths for integer programming and links to artificial intelligence”, Computers and Operations Research 13(5): 533–549.
  • Glover, F.; Laguna, M.: Martí, R. (2003) “Scatter search”, in Advances in Evolutionary Computing, Springer Berlin Heidelberg: 519–537.
  • Guo, S.; Ying, K.; Lim, A.; Wang, F. (2004) “A new neighborhood based on improvement graph for robust graph coloring problem”, in: G.I. Webb...
  • Gutiérrez-Andrade, M.A.; Lara-Velázquez, P.; López-Bracho, R.; Ramírez-Rodríguez, J.(2010) “Heuristics for the robust coloring problem”, Revista...
  • Gómez, D.; Montero, J.; Yáñez, J.; Poidomani, C. (2007) “A graph coloring approach for image segmentation”, Omega 35(2): 173–183.
  • Kong, Y.; Wang, F.; Lim, A.; Guo, S. (2003) “A new hybrid genetic algorithm for the robust graph coloring problem”, in: T.D. Gedeon &...
  • Kruskal, J.B. (1956) “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical...
  • Kumar, V. (1992) “Algorithms for constraint-satisfaction problems: A survey”, AI magazine 13(1): 32–44.
  • Lara-Velázquez, P.; Gutiérrez-Andrade, M.A.; Ramírez-Rodríguez, J.; López-Bracho, R. (2005) “Un algoritmo evolutivo para resolver el problema...
  • Laureano-Cruces, A.L.; Ramírez-Rodríguez, J.; Hernández-González, D.E.; Méndez-Gurrola, I.I. (2011) “An ant colony algorithm for the robust...
  • Leus, R.; Herroelen, W. (2007) “Scheduling for stability in single-machine production systems”, Journal of Scheduling 10: 223–235.
  • Lim, A.; Wang, F. (2004) “Metaheuristics for robust graph coloring problem”, Proceedings of the 16th IEEE International Conference on Tools...
  • Lim, A.; Wang, F. (2005) “Robust graph coloring for uncertain supply chain management”, Proceedings of the 38th Hawaii International Conference...
  • Liu, Z.(1998) Algorithms for Constraint Satisfaction Problems (CSPs). Master of Mathematics in Computer Science, University of Waterloo, Canada.
  • Maniezzo, V.; St’́utzle, T.; Voβ, S. (Editors) (2009) Matheuristics. Hybridizing Metaheuristics and Mathematical Programming, Volume 10. Springer,...
  • Martí, R.; Laguna, M. (2003) “Scatter search: Diseño básico y estrategias avanzadas”, Inteligencia Artificial, Revista Iberoamericana de Inteligencia...
  • Mora-Gutiérrez, R.A.; Ramírez-Rodríguez, J.; Rincón-García, E. (2012) “An optimization algorithm inspired by musical composition”, Artificial...
  • Mora-Gutiérrez, R.A.; Ramírez-Rodríguez, J.; Rincón-García, E.; Ponsich, A.; Herrera, O. (2012) “An optimization algorithm inspired by social...
  • Mora-Gutiérrez, R.A. (2013) Diseño y Desarrollo de un Método Heurístico Basado en un Sistema Socio-Cultural de Creatividad para la Resolución...
  • Mora-Gutiérrez R.A.; Rincón-García, E.A.; Ramírez-Rodríguez, J.; Ponsich, A.; Herrera-Alcántara, O.; Lara-Velázquez, P. (2013) “An optimization...
  • Mora-Gutiérrez, R.A.; Rincón-García, E.A.; Ramírez-Rodríguez, J.; Ponsich, A.; Herrera-Alcántara, O.; Lara-Velázquez, P. (2013) “Adaptation...
  • Pardalos, P.; Mavridou, T.; Xue, J. (1998) “The graph coloring problem: A bibliographic survey”, in: D.Z. Du & P.M. Pardalos (Eds.) Handbook...
  • Ramírez-Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis de Doctorado, Universidad Complutense, Madrid, España....
  • Yáñez, J.; Ramírez, J. (2003) “The robust coloring problem”, European Journal of Operational Research 148(3): 546–558.
  • Wang, F.; Xu, Z. (2013) “Metaheuristics for robust graph coloring”, Journal of Heuristics 19(4): 529–548.
  • de Werra, D. (1996) “Extensions of coloring models for scheduling purposes”, European Journal of Operations Research 92(3): 474–492.
  • de Werra, D. (1996) “Some combinatorial models for course scheduling”, in: E. Burke & P. Ross (Eds.) Practice and Theory of Automated...