Algoritmo Heurístico para el Problema del Vertex Separation

Abstract

La tem¿atica de este Proyecto Fin de Carrera se enmarca dentro del ¿area de la optimizaci ¿on. Particularmente se centra en la resoluci¿on de un problema espec¿¿fico: el problema Vertex Separation. El objetivo del proyecto es encontrar heur¿¿sticas que permitan abordar el problema de forma eficiente, generando soluciones de buena calidad. Este proyecto no esta orientado al desarrollo de una aplicaci¿on de usuario, sino que est¿a m¿as cercano a un proyecto de investigaci¿on. En ¿el, se har¿a una introducci¿on al mundo de la optimizaci¿on, donde se hablar¿a sobre los distintos tipos de problemas de optimizaci¿on, su complejidad algor¿¿tmica, las metodolog¿¿as para abordarlos y el software existente para optimizaci¿on. Se har¿a una incursi¿on en los m¿etodos exactos y se comprobar¿a, a trav¿es de la experimentaci ¿on, que este tipo de m¿etodos resultan ineficientes para la resoluci¿on de este problema, cuando el tama¿no de la entrada es grande. Tambi¿en se documentar¿an algunos de los m¿etodos aproximados m¿as relevantes. Por un lado se introducir¿an los m¿etodos heur¿¿sticos, explicando en qu¿e consisten, cu¿ales son sus ventajas y qu¿e inconvenientes presentan. Por otro lado, se introducir¿a el concepto de t¿ecnica metaheur¿¿stica, se explicar¿an las ventajas e inconvenientes de este tipo de t¿ecnicas y, a partir de los resultados experimentales, se mostrar¿a como, este tipo de m¿etodos, consiguen soluciones de muy buena calidad en un tiempo razonable. Por ¿ultimo, se analizar¿an detalladamente los resultados obtenidos para determinar cu¿al de las t¿ecnicas propuestas, es la más eficaz.