Algoritmos de aproximación para el problema de Steiner con penalidades

Abstract

El objeto de estudio de este informe es algoritmos de aproximación aplicados al problema del árbol de Steiner con penalidades (PCST por sus siglas en inglés). El problema consiste en diseñar una subred de costo mínimo que conecte a todos o algunos nodos clientes con una central, donde la no conexión de un cliente tiene una correspondiente penalización y la subred solución debe ser un árbol. La motivación a este trabajo parte de la necesidad de asignar un conjunto de generadores eólicos en un parque, en ciertos lugares factibles predefinidos, donde además existen penalizaciones por aquellos lugares que queden sin un generador. El problema consiste en encontrar una subred que interconecte los lugares con generador donde se minimice el costo de la red más las penalizaciones por los lugares que queden vacíos. El problema puede considerar un nodo particular (nodo raíz) el cual debe pertenecer a la subred solución. Como punto de partida se realiza un análisis de las principales metodologías para atacar el problema, un repaso de los conceptos más importantes de complejidad computacional y luego un estudio enfocado a algoritmos de aproximación existentes para el PCST. La parte fundamental de este trabajo está enfocada en el análisis, comprensión e implementación de un algoritmo de aproximación factor 2 que sigue el esquema primal-dual con sincronización (propuesto por Michel X. Goemans y David P. Williamson), así como sus posibles variantes que incluyan aleatorización. Se estudian resultados obtenidos sobre instancias estándares ya estudiadas en otros trabajos académicos. Los resultados que se obtienen determinan que el algoritmo tiene un comportamiento muy bueno en cuanto al compromiso entre tiempos de ejecución y valores objetivo. En cuanto a las variantes planteadas, existen algunos casos en los que se obtienen mejores resultados que con el algoritmo original. Por último se presentan las conclusiones y trabajo a futuro.