Defensa Tesis Licenciatura Hernán Berinsky

• Alumno: Hernán Berinsky
• Título: Un modelo y algoritmo branch-and-cut para el problema del m-anillo-estrella con capacidades
• Directora: Paula Zabala
• Jurados: Irene Loiseau, Javier Marenco
• Resumen:

El Problema del m-anillo-estrella con capacidades (CmRSP) consiste en encontrar una estructura llamada m-anillo-estrella de costo mínimo que conecte a un conjunto de clientes en red. La estructura está compuesta por conexiones anillo (con costos asociados) que forman m anillos (ciclos) disjuntos de nodos junto con un nodo distinguido (depósito) común a todos los anillos, y conexiones estrella (con costos asociados) que permiten conectar clientes a anillos. Adicionalmente, existen nodos de tránsito, llamados nodos de Steiner que pueden ser utilizados opcionalmente en los anillos en casos que permitan reducir costos al conectar clientes a estos nodos con conexiones estrella. Cada anillo, además, tiene una capacidad de clientes, esto quiere decir que no se puede superar un cierto límite de cantidad de clientes en cada anillo, considerando tanto los clientes que forman parte del anillo como aquellos que están conectados a algún nodo del anillo por medio de una conexión estrella. CmRSP pertenece a la clase de problemas NP-Hard.

El objetivo de esta tesis es abordar el Problema del m-anillo-estrella con capacidades bajo un enfoque de programación lineal entera, desarrollando un algoritmo branch-and-cut para su resolución exacta.