Keywords
combinatorial optimization
integer programming
metaheurísticas
optimización combinatoria
programación entera
How to Cite
Abstract
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.
References
Archetti, C.; Bianchessi, N.; Hertz, A. (2014) “A branch-and-price algorithm for the robust graph coloring problem”, Discrete Applied Mathematics 165(11): 49–59.
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 Research 119(3): 557–581.
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): 565–571.
Chams, M.; Hertz, A.; de Werra, D. (1987) “Some experiments with simulated annealing for coloring graphs”, European Journal of Operational Research 32(2): 260–266.
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 & X. Yu (Eds.) AI 2004: Advances in Artificial Intelligence, LNAI 3339, Springer, Berlin: 636–645.
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 de Matemática: Teoría y Aplicaciones 18(1): 137–147.
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 & L.C.C. Fung (Eds.) Lecture Notes in Artificial Intelligence, Vol. 2903, Springer: 125–136.
Kruskal, J.B. (1956) “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical Society 7(1): 48–50.
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 de coloración robusta”, Revista de Matemática: Teoría y Aplicaciones 12(1-2): 111–120.
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 graph coloring problem”, ICGST AIML-11 Conference, Dubai: 57–60.
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 with Artificial Intelligence (ICTAI 2004): 514–518.
Lim, A.; Wang, F. (2005) “Robust graph coloring for uncertain supply chain management”, Proceedings of the 38th Hawaii International Conference on System Sciences: 1–10.
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, New York.
Martí, R.; Laguna, M. (2003) “Scatter search: Diseño básico y estrategias avanzadas”, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial 7(19): 123–130.
Mora-Gutiérrez, R.A.; Ramírez-Rodríguez, J.; Rincón-García, E. (2012) “An optimization algorithm inspired by musical composition”, Artificial Intelligence Review: 1–15.
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 creativity systems”, Computing 94(11): 887–914.
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 de Problemas de Optimización Continuos no Lineales y Diseño de Zonas Electorales. Tesis de Doctorado, Universidad Nacional Autónoma de México, México.
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 algorithm inspired by musical composition in constrained optimization problems”, Revista de Matemática: Teoría y Aplicaciones 20(2): 183–202.
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 of the musical composition method for solving constrained optimization problems”, Soft Computing 18(10): 1931–1948.
Pardalos, P.; Mavridou, T.; Xue, J. (1998) “The graph coloring problem: A bibliographic survey”, in: D.Z. Du & P.M. Pardalos (Eds.) Handbook of Combinatorial Optimization, Vol 2, Kluwer, New York: 331–395.
Ramírez-Rodríguez, J. (2001) Extensiones del Problema de Coloración de Grafos. Tesis de Doctorado, Universidad Complutense, Madrid, España. http://eprints.ucm.es/4479/, accessed March 26, 2014.Régin, J.C. (1994) “A filtering algorithm for constraints of difference in CSPs”, Proceedings of AAAI, Vol. 1: 362–367.
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 Timetabling, Lecture Notes in Computer Science 1153, Springer: 296–308.
Comments
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright (c) 2016 Revista de Matemática: Teoría y Aplicaciones