Defensa Tesis Licenciatura Soledad Ramusio Mora

• Título: Un algoritmo branch and cut para el problema de asignación de frecuencias en sistemas de radio punto a multipunto
• Alumna: Soledad Ramusio Mora
• Director: Dr. Javier Marenco
• Jurados: Dra. Flavia Bonomo y Dra. Paula Zabala
• Resumen:

Los sistemas de radio punto a multipunto son conjuntos de antenas de radio que proveen acceso inalámbrico a redes de comunicación de voz y datos. Este tipo de sistemas debe ser operado utilizando un cierto espectro de frecuencias de radio, lo cual normalmente produce problemas de capacidad. Por lo tanto es necesario reutilizar frecuencias, pero este reuso no debe generar interferencia entre las señales. El problema de determinar las frecuencias para los enlaces se conoce como el problema de asignación de frecuencias en sistemas de radio punto a multipunto. Este problema es NP-hard, y no existen algoritmos aproximados polinomiales con una garantía de calidad fija para el mismo. Como los métodos de planos de corte han demostrado ser efectivos para muchos otros problemas de optimización combinatoria, el objetivo de esta tesis es aplicar este tipo de algoritmos al problema de asignación de frecuencias en sistemas punto a multipunto.

En esta tesis se describe la implementación de un algoritmo Branch & Cut para este problema, realizada con el entorno Abacus. Esta implementación toma como base un modelo de programación lineal entera existente para el problema, y se utilizan en el algoritmo todas las familias de desigualdades conocidas para esta formulación. Sobre la base de esta implementación, se realizan experimentos computacionales para evaluar empíricamente la calidad de las desigualdades váalidas con el fin de definir las familias más efectivas, y se presentan estos resultados y los obtenidos variando los diferentes parámetros de la implementación. Estos experimentos se realizaron sobre instancias que intentan representar escenarios reales. Los resultados obtenidos con el algoritmo son muy prometedores y permiten resolver en forma óptima instancias que no podían ser resueltas con las herramientas computacionales existentes. Como parte de la implementación, se proponen dos heurísticas primales de redondeo, una de las cuales está basada en la resolución de un modelo sencillo de programación lineal.