Defensa Pública de la Tesis de Maestría en Investigación de Operaciones de la Lic. Nicole Rosenstock Cukrowicz.
Fecha: Viernes 22 de Febrero de 2019.
Hora: 13:00
Lugar: Salón de Rojo de Posgrados (703), Facultad de Ingeniería, Séptimo piso, UDELAR.
Título de la tesis: "GRASP Optimization for the Stochastic Weighted Graph Fragmentation Problem".
Director de Tesis: Dr. Pablo Romero,
Co-Director de Tesis: Dr. Juan Piccini,
Director Académico: Dr. Franco Robledo.
Tribunal:
• Dr. Guillermo Durán (Director del Instituto de Cálculo - Facultad de Ciencias Exactas y Naturales, UBA).
• Dr. Elvio Accinelli (Facultad de Economía, Profesor, Universidad Autónoma de San Luis Potosí, México).
• Dr. Jorge Pérez Zerpa (Instituto de Estructuras y Transporte (IET), Facultad de Ingeniería, UDELAR).
• Dr. Pedro Piñeyro (Dpto. de Investigación Operativa - InCo, Facultad de Ingeniería, UDELAR).
RESUMEN:
Los nodos críticos juegan un rol fundamental en la conectividad de las redes.
Su identificación es importante para el diseño de estrategias eficientes para
prevenir que tanto un software malicioso como una epidemia se propaguen por
la red. En este contexto, el Stochastic Weighted Graph Fragmentation Problem
(SWGFP) es un problema de optimización combinatoria perteneciente a la
clase de problemas NP-Completos. El objetivo consiste en miniminizar
el impacto de un ataque aleatorio en un nodo de la red, seleccionando
adecuadamente nodos a inmunizar con un presupuesto acotado. En el SWGFP
se asume que el ataque sigue una ley de probabilidad conocida en los
nodos, y que afecta a toda la componente conexa del nodo seleccionado. En
esta tesis se desarrolla una solución GRASP enriquecida con Path-Relinking
para abordar el SWGFP. Se estudia el rendimiento de la propuesta ante
tres escenarios de ataque, en comparación con una variante de GRASP
anteriormente desarrollada de la literatura y una heurística aleatoria o
Random para el problema en la cual los nodos son elegidos al azar. Los
experimentos computacionales muestran que el algoritmo basado en Conjuntos
Independientes que se desarrolla en esta tesis, presenta un mejor desempeño
que los dos restantes, con valores inferiores del número esperado de pérdidas
y mayor robustez.
Palabras claves:
Optimización combinatoria, Nodos críticos, GRASP, Path Relinking, Complejidad computacional.