BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Departamento de Computación
X-ORIGINAL-URL:https://www.dc.uba.ar
X-WR-CALDESC:Eventos para Departamento de Computación
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Sao_Paulo
BEGIN:STANDARD
TZOFFSETFROM:-0300
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20211110T090000
DTEND;TZID=America/Sao_Paulo:20211110T110000
DTSTAMP:20260503T140838
CREATED:20211104T122232Z
LAST-MODIFIED:20211104T122232Z
UID:7132-1636534800-1636542000@www.dc.uba.ar
SUMMARY:Defensa Tesis Doctorado Emanuel Delgadillo
DESCRIPTION:Título: Un algoritmo branch-and-price and cut para diseño de redes con p-ciclos \nDirectora: Irene Loiseau \nJurados: \n– Elena Fernández Aréizaga\,Universidad de Cádiz\, España.\n– Celso Carneiro Ribeiro\, Universidad Federal Fluminense\, Brasil.\n– Héctor Cancela\, Universidad de la República\, Uruguay. \nLink a la transmisión por YouTube: https://youtu.be/LRA38dX81-o \n———————————————————————————————————- \nRESUMEN: \nEl concepto de redes de p-ciclos se introdujo a fines de los años 90 en el contexto de\nredes ópticas supervivientes. Una red de comunicaciones se dice superviviente si puede\ncontinuar brindando servicio pese a la falla de alguno de sus componentes. Las topologías\nbasadas en p-ciclos combinan las mejores características para asegurar la supervivencia:\nvelocidad en la recuperación y poca capacidad redundante\, lo que implica menor costo.\nUn p-ciclo es un ciclo preconfigurado formado por un canal de reserva en cada enlace que\nlo compone. Cada p-ciclo protege a todos los enlaces que forman el ciclo y también a cada\nenlace que no es parte del ciclo pero cuyos nodos s lo son.\nA partir de la necesidad de diseñar redes basadas en p-ciclos de costo mínimo\, surgieron\nvarios problemas de optimización combinatoria\, de los cuales el mas elemental es el\nproblema de Asignación de Capacidad de Reserva (Spare Capacity Allocation – SCA). En\neste problema se tiene una red con demandas asociadas a cada enlace previamente asignadas.\nSe debe determinar la disposición de la capacidad de reserva mediante la ubicación\nde p-ciclos de forma que quede garantizada la recuperación de las comunicaciones ante la\nfalla de alguno de sus enlaces. Cada enlace adicional de reserva incrementa el costo de la\nsolución\, que debe ser minimizado.\nEn este trabajo desarrollamos un algoritmo branch-and-price-and-cut para SCA. Para\neso presentamos una nueva formulación como problema de programación lineal entera\, la\ncual que tiene una estructura diagonal en bloque usual en este tipo de problemas. A partir\nde esta formulación aplicamos la descomposición Dantzig-Wolfe para obtener el problema\nmaestro y el problema de pricing. Con la descomposición eliminamos el inconveniente\nde la simetría proveniente de la estructura diagonal de la formulación original\, aunque\ntambién mostramos que el problema de pricing resultante es NP-hard. Detallamos las\nmodificaciones necesarias que permiten aplicar reglas de branching y planos de corte en el\nproblema maestro sin modificar la estructura del problema de pricing en la mayoría de los\ncasos\, y realizando modificaciones poco significativas en otros. Resolvemos las instancias\nde pricing de forma exacta\, y también proponemos heurísticas para esto\, con el objetivo\nde acelerar el proceso de generación de columnas.\nPara la experimentación contamos con instancias correspondientes a redes reales para\ncomparar nuestro algoritmo con trabajos previos y generamos instancias mas grandes para\nevaluar los distintos parámetros. Los resultados obtenidos mostraron ser muy superadores\nrespecto a trabajos anteriores para este problema.
URL:https://www.dc.uba.ar/event/defensa-tesis-doctorado-emanuel-delgadillo/
LOCATION:YouTube
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR