Implementación de framework de evaluación para los problemas del máximo conjunto independiente y máximo corte

Abstract

Las redes neuronales son cada vez más populares. La creación de redes neuronales que funcionan sobre grafos o GNNs (Graph Neural Network) se ha presentado como una nueva oportunidad de abordar la amplia gama de problemas que se pueden modelar con grafos, problemas que van desde el comercio virtual hasta la bioinformática. El área de optimización combinatorial ha sido una en la que ha habido interés particularmente debido a sus numerosos problemas importantes con muchas aplicaciones que son NP y difíciles de aproximar. Sin embargo, estos problemas tienen una larga historia de estudio, a lo largo de los años múltiples algoritmos se han desarrollado para tratar de obtener buenos resultados en estos problemas. También se han tratado de buscar instancias difíciles que puedan representar bien los desafíos que conllevan estos problemas. El problema que existe es que al momento de querer desarrollar una GNN es muy fácil pasar por alto alguno de los algoritmos importantes o no encontrar los casos de prueba indicados con los que evaluar la red, si un algoritmo nuevo no se evalúa apropiadamente se pueden llegar a conclusiones erróneas con respecto a su desempeño, es importante tener claro el estado del problema para poder desarrollar un algoritmo de forma correcta. Para solucionar este problema, este trabajo plantea un framework para organizar la evaluación de algoritmos y generar un benchmark apropiado para estos problemas. Además, se crean dos instancias del framework sobre los problemas de Máximo Conjunto Independiente y Máximo Corte, con esto se deja disponible una herramienta que permite comparar el desempeño de nuevos algoritmos para estos problemas con algoritmos clásicos que funcionan al estado del arte sobre instancias relevantes del problema.