Diseño e implementación de un algoritmo GRASP para el problema de coloración de grafos
Resumen
Una de las dificultades en la búsqueda de la solución óptima a problemas de optimización combinatoria es el elevado costo computacional para obtenerlas. Por ello se hace necesaria la utilización de algoritmos basados en metaheurísticas para obtener soluciones factibles a un costo computacional razonable. En este contexto, en el presente trabajo se aborda el diseño de una heurística basada en la metodología GRASP para el Problema de Coloración de Grafos. Este algoritmo se lo ha implementado en Mathematica 8.0.4.0 ® y ejecutado con diversas instancias del problema para medir la calidad del mismo.
Citas
DING-ZHUE DU AND PANOS M. PARDALOS. (2005). "Handbook of combinatoria! optimization". Volume B, Springer.
MCCOLLUM B., MCMULLAN P. (2007). "The Second lnternational Timetabling Competition: Examination Timetabling Track". Technical Report. Queen's University Belfast.
DING-ZHUE DU AND PANOS M. PARDALOS" (2005). Handbook of combinatorial optimization", Volume B, Springer
ZHIPENG LU, JIN-KAO HAO. (2009). "A memetic algorithm for graph coloring", European Journal of Operations Research, ELSEVIER
AVANTHAY C., HERTZ A., ZUFFEREY N. (2003). "A variable neighborhood search for graph coloring". European Joumal of Operational Research, ELSEVIER.
A. HERTZ, D. DE WERRA. (1987). "Using Tabu Search Techniques for Graph Coloring. Computing". By Springer-Verlag.
C.LUCET, F. MENDES, A. MOUKRIM. (2004). "An Exact method for graph coloring. Computer & Operations Research'', ELSEVIER.
MÉNDEZ I., ZABALA P. (2007). "A cutting plane algorithm for graph coloring. Discrete Applied Mathematics".ELSEVIER.
EIBEN A., VAN DER HAUW J., VAN HENNERT J. "Graph Co/oring with Adaptive Evo/utionary Algorithms". Joumal of Heuristics, volume 4: l.
BODLAENDER H., KRATSCH D. (2006). "An exact algorithm for graph coloring with polynomial memory''. Utrecht University.
JOHNSON D., ARAGÓN C., MCGEOCH L., SCHEVON C. (1990). "Optimization by simulated annealing: An Experimental Evaluation; Part lI, Graph Coloring and Number Partition, Operations Research Society of America".
SOPENA E. (2001). "Oriented Graph Coloring'', ELSEVIER.
WERRA, D. (1990). "Heuristics for Graph Coloring, Compute" Computational Graph Theory, Suppl. 7, Springer, Vienna, 191- . 208.
BRÉLAZ, D. (1979). "New methods to color the vertices of a graph", Communications of the Assoc. of Com- put. Machinery 22, 251- 256.
JOHNSON, D. S., ARAGON, C. R., MCGEOCH, L.A., AND SCHEVON, C. "Optimization by simulated annealing: An experimental evaluation; part ii, graph coloring and number partitionin ft'. Operations Research, 39(3):378406.
RESENDE M., RIBEIRO C. (2002). "Greedy Randomized Adaptive Search Procedures",AT&T Labs Research Technical Report. Hanbook in Metaheuristic, Fred Glover.
GLOVER FRED, KOCHENBERGER. (2003). "HandBook of Metaheuristics'', Intemational Series in Operations Research & Management Science.
TALBI EL-GHAZALI. (2009). "Metaheristics from design to implementaction", John Wiley & Sons, Inc., Hoboken, New Jersey.
MCCOLLUM B., MCMULLAN P. (2007). "The Second lnternational Timetabling Competition: Examination Timetabling Track". Technical Report. Queen's University Belfast.
DING-ZHUE DU AND PANOS M. PARDALOS" (2005). Handbook of combinatorial optimization", Volume B, Springer
ZHIPENG LU, JIN-KAO HAO. (2009). "A memetic algorithm for graph coloring", European Journal of Operations Research, ELSEVIER
AVANTHAY C., HERTZ A., ZUFFEREY N. (2003). "A variable neighborhood search for graph coloring". European Joumal of Operational Research, ELSEVIER.
A. HERTZ, D. DE WERRA. (1987). "Using Tabu Search Techniques for Graph Coloring. Computing". By Springer-Verlag.
C.LUCET, F. MENDES, A. MOUKRIM. (2004). "An Exact method for graph coloring. Computer & Operations Research'', ELSEVIER.
MÉNDEZ I., ZABALA P. (2007). "A cutting plane algorithm for graph coloring. Discrete Applied Mathematics".ELSEVIER.
EIBEN A., VAN DER HAUW J., VAN HENNERT J. "Graph Co/oring with Adaptive Evo/utionary Algorithms". Joumal of Heuristics, volume 4: l.
BODLAENDER H., KRATSCH D. (2006). "An exact algorithm for graph coloring with polynomial memory''. Utrecht University.
JOHNSON D., ARAGÓN C., MCGEOCH L., SCHEVON C. (1990). "Optimization by simulated annealing: An Experimental Evaluation; Part lI, Graph Coloring and Number Partition, Operations Research Society of America".
SOPENA E. (2001). "Oriented Graph Coloring'', ELSEVIER.
WERRA, D. (1990). "Heuristics for Graph Coloring, Compute" Computational Graph Theory, Suppl. 7, Springer, Vienna, 191- . 208.
BRÉLAZ, D. (1979). "New methods to color the vertices of a graph", Communications of the Assoc. of Com- put. Machinery 22, 251- 256.
JOHNSON, D. S., ARAGON, C. R., MCGEOCH, L.A., AND SCHEVON, C. "Optimization by simulated annealing: An experimental evaluation; part ii, graph coloring and number partitionin ft'. Operations Research, 39(3):378406.
RESENDE M., RIBEIRO C. (2002). "Greedy Randomized Adaptive Search Procedures",AT&T Labs Research Technical Report. Hanbook in Metaheuristic, Fred Glover.
GLOVER FRED, KOCHENBERGER. (2003). "HandBook of Metaheuristics'', Intemational Series in Operations Research & Management Science.
TALBI EL-GHAZALI. (2009). "Metaheristics from design to implementaction", John Wiley & Sons, Inc., Hoboken, New Jersey.
