Diseño robusto de red overlay mediante heurísticas y codificación de modelo exacto

Abstract

El presente trabajo tiene como objetivo definir el diseño óptimo de una red overlay que se modela en dos capas: una red de datos y una red de transporte que permiten separar respectivamente, que nodos se conectan y con que volumen de tráfico, de las rutas físicas y reales que estos tráficos recorren. Se definirá que enlaces de la red de datos deben participar de la solución y para cada uno se hallará la asignación óptima de tecnología (cada tecnología se corresponde con una capacidad diferente). Esta asignación de tecnologías deberá contemplar las demandas de tráfico entre los nodos, estás demandas son dato del problema. Los nodos de la red de datos son conocidos y no variarán. Para cada enlace incluido en la red de datos, se deberá fijar el camino que recorrerá el tráfico correspondiente, en la red de transporte.Como principal condición la red a hallar deberá ser robusta respecto a una falla simple, esto quiere decir que si en la red de transporte falla uno (solo uno a la vez) de los enlaces, las demandas se deben seguir cumpliendo. Se deberá garantizar para cada demanda, un camino alternativo en la red de datos cuando uno de los enlaces físicos del camino típico falla. Para lograr esto se implementaron dos heurísticas que calculan una solución aproximada y también se implemento un algoritmo Branch and Bound para hallar una solución óptima. La primera heurística implementada buscaba una solución inicial que sirviera de punto de partida para el algoritmo Branch and Bound. En tal sentido y por la temprana familiarización con el problema, se logró rápidamente una solución factible pero que descuida aspectos importantes para lograr una solución aproximada a la óptima. Paralelamente, a partir de un modelo lineal binario del problema, que nos fue proporcionado, se diseño un algoritmo Branch and Bound para encontrar una solución exacta.

Se encontró que el software Cplex ya contaba con la implementación de algoritmos Branch and Cut (que es una variante de Branch and Bound), por lo que se utilizaron sus bibliotecas para implementarlo. Por último al notar que el algoritmo Branch and Bound no lograba hallar la solución para nuestro caso real (por las dimensiones del problema), se implementó una segunda heurística. Esta vez al pretender la solución final y por tener una gran vinculación con el problema, se obtuvo una heurística que contempla todos los aspectos a optimizar y logra una buena solución.