Fecha: Viernes 22 de agosto de 2014
Hora: 15:00
Lugar: Sala de Posgrados, Instituto de Computación, Facultad de Ingeniería
Título de la tesis: "Diseño Topológico de Redes. Caso de Estudio: The Capacitated m Two-Node Survivable Star Problem"
Director Académico: Dr. Franco Robledo (Instituto de Computación, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
Directores de Tesis: Dr. Franco Robledo y Dr. Antonio Mauttone (Instituto de Computación, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
Tribunal:
- Dra. Simone de Lima Martins (Departamento de Ciência da Computação, Instituto de Computação, Universidade Federal Fluminense, Brasil) -Revisora-
- Dr. Pablo Rodríguez-Bocca (Instituto de Computación, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
- Dr. Marcos Viera (Instituto de Computación, Facultad de Ingeniería, UdelaR / PEDECIBA Informática)
Resumen:
Hoy en día prácticamente todas las actividades inherentes al ser humano tienen un soporte de hardware y software que las gestiona o las controla. Los elementos de comunicaciones cumplen un papel vital en este entramado. El diseño de topologías de redes tolerantes a fallo ha pasado a tener una importancia fundamental en la infraestructura de estas redes y constituye un elemento crítico a la hora de mantener la comunicación ante la falla de un enlace o alguno de sus nodos. El problema tratado en esta tesis intenta resolver eficientemente el diseño de una red con conexiones redundantes utilizada a menudo por los operadores telefónicos y servicios de internet. Dicha red conecta un nodo principal con clientes y establece algunas normas que modelan su construcción, tales como cantidad de clientes, número de componentes y tipos de enlaces, con el fin de satisfacer restricciones técnicas y necesidades operativas.
Se considera en este trabajo un problema de optimización combinatoria denominado CmTNSSP (Capacitated m Two-Node-Survivable Star Problem), una relajación del problema CmRSP (Capacitated m Ring Star Problem). La variante relajada consiste en que los anillos (rings) del problema CmRSP pueden ser componentes 2-nodo-conexas, las cuales no necesariamente deben ser ciclos.
El objetivo de esta tesis consta de la especificación de un modelo de programación matemáticadel problema a tratar, la resolución exacta mediante un lenguaje algebraico y un solver, y la resolución aproximada del mismo a través de una metaheurística que alterna búsquedas locales que obtienen soluciones incrementalmente mejores y búsquedas locales de resolución exacta basadas en modelos de programación matemática, en particular Programación Lineal Entera. Los resultados computacionales obtenidos por los algoritmos desarrollados muestran la robustez y competitividad de los mismos, comparados con las instancias benchmark publicadas en la literatura. Así mismo los experimentos muestran la relevancia de considerar la variante concreta del problema estudiado en esta tesis.
Palabras Clave: Diseño Topológico de Redes, Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), Metaheurísticas, Programación Lineal Entera, Optimización.