Algoritmos eficientes para problemas de grafos

El objetivo central del proyecto es diseñar algoritmos eficientes para problemas de grafos, previo estudio de su tratabilidad. Nos centramos, en particular, en los problemas de coloreo y transversal en hipergrafos de intersección y en el problema de diseño de redes. Asimismo, estudiamos distintas clases de grafos, enfocándonos en los problemas de reconocimiento, certificación y representación. El objetivo es poder estudiar los problemas combinatorios sobre las clases estudiadas, aprovechando sus particularidades.

Para el diseño de los algoritmos, utilizamos distintos enfoques metodológicos. Cuando el problema en cuestión es tratable, proponemos desarrollar algoritmos con una complejidad asintótica menor a la conocida actualmente. Para ello, estudiamos las propiedades estructurales de los grafos considerados que permiten hacer un uso eficiente de los recursos, y diseñamos algoritmos y estructuras de datos específicas para estos problemas. Cuando el problema es intratable, el objetivo es diseñar algoritmos eficientes que brinden mejores soluciones a las ya conocidas en un tiempo comparable. En este proyecto consideramos dos técnicas conocidas para los problemas intratables. La primera es el uso de metaheurísticas que exploren inteligentemente el espacio de soluciones factibles. La dificultad de diseñar un algoritmo metaheuristico está en decidir cómo se explora el espacio, y cómo se implementa eficientemente cada algoritmo que lo compone. La segunda es la aplicación de algoritmos del estilo branch-and-bound (branch-and-cut, branch-and-price, etc), en las que se inspecciona un árbol de búsqueda. La dificultad en este caso está en cómo resolver cada nodo del árbol (aplicando heurísticas y relajaciones lineales) y en decidir el orden en el que se procesan los mismos a fin de acotar el espacio de búsqueda usando la menor cantidad de tiempo posible. Esta técnica requiere la formulación de un modelo de programación lineal entera que define el espacio de búsqueda.

Finalmente, también consideramos la tratabilidad de los problemas en cuestión, que es un paso previo necesario para determinar qué técnica conviene aplicar para resolver un problema.

Además del avance en el estado del arte en los problemas estudiados, esperamos conformar un grupo de estudio de temas de investigación operativa, particularmente en el estudio de algoritmos en grafos. Esperamos una repercusión positiva en la formación de los alumnos de grado de la incipiente Licenciatura en Desarrollo de Software en un tema particularmente útil para el sector productivo.