[Todos CMAT] Defensa Tesis Maestría Ing. Rodrigo Recoba: viernes 21 de Agosto, 17:00 horas

[Ing. Franco Robledo]

Estimados Sres. Investigadores, Docentes y Estudiantes:

Nos complace anunciarles que el viernes 21 de Agosto se llevará a cabo  
la Defensa Pública de la Tesis de Maestría en Informática del PEDECIBA  
del Ing. Rodrigo Recoba Viana.

A continuación encontrarán los detalles del evento.

Están todos cordialmente invitados.

Saludos,

Franco Robledo

------------------------------------------------------------------------

Fecha: Viernes 21 de Agosto de 2015

Hora: 17:00

Lugar: Salón Rojo, Séptimo Piso, Facultad de Ingeniería (Cuerpo  
Central, Piso 7)

Título de la tesis: "Diseño Topológico de Redes. Caso de Estudio  
“2-Node-Connected Star Problem”."

Director de Tesis: Dr. Ing. Franco Robledo.

Tribunal:
- Dr. Víctor Albornoz (USM, Chile) - Revisor -
- Dr. Ing. Daniel Kofman (Telecom ParisTech, Francia)
- Dr. Ing. Pablo Sartor  (Universidad de Montevideo)
- Dr. Ing. Pedro Piñeyro (Instituto de Computación, Facultad de  
Ingeniería, UdelaR / PEDECIBA Informática)
- Dra. Ing. Aiala Rosá   (Instituto de Computación, Facultad de  
Ingeniería, UdelaR / PEDECIBA Informática)


Resumen:

En este trabajo estudiamos un nuevo problema de optimización  
combinatoria al que denominamos 2NCSP (Two-Node Connected Star  
Problem), el cual se inspira en el conocido "Ring Star Problem". La  
principal diferencia consiste en que la componente 2-nodo conexa del  
backbone no tiene que tener necesariamente topología de anillo,  
buscando encontrar de esta forma, soluciones de menor costo,  
manteniendo los mismos requisitos de conectividad.

El objetivo de este trabajo es definir formalmente el problema  
"Two-Node Connected Star Problem" y su resolución mediante un  
algoritmo GRASP de buen desempeño. Se diseñaron e implementaron  
búsquedas locales basadas en Modelos de Programación Lineal Entera y  
búsquedas locales que generan movimientos tradicionales para este tipo  
de problemas.

Los resultados obtenidos muestran una buena performance del algoritmo  
en relación a instancias de prueba diseñadas y publicadas por otros  
autores. Dichas instancias de prueba consideran grafos de entre 50 y  
200 nodos de la TSPLIB, donde los costos de asignación y conexión se  
obtienen con un factor de ponderación de la distancia euclidiana entre  
los nodos. Dicho factor permite determinar que la componente 2-nodo  
conexa de la solución deba contener la mayoría de los nodos, o solo  
unos pocos.

Palabras Clave: Diseño Topológico de Redes, Greedy Randomized Adaptive  
Search Procedure (GRASP), Optimización, Ring Star Problem (RSP).