Integer Programming Models for the RSA

BIANCHETTI, MARCELO

Ciudad Autónoma de Buenos Aires

Workshop; Workshop in Operations, Networks and Data Analytics; 2016

Universidad Di Tella

La soluci ́on m ́as prometedora para la creciente demanda de tr ́afico en redes de comunicaciones consiste en la aplicaci ́on de t ́ecnicas de uso flexible del cableado de fibra ́optica, en particular en cuanto a la tecnolog ́ıa de grilla flexible (flexgrid) especificada en el est ́andar ITU-T G.694.1. En esta especificaci ́on, el espectro de frecuencias de un enlace de fibra ́optica se divide em slots pequen ̃os, y cualquier secuencia de slots consecutivos se puede utilizar como un u ́nico canal. Un canal puede ser ruteado a trav ́es de la red de fibra ́optica, formando as ́ı un lightpath.En este tipo de redes, el problema de establecer lightpaths que satisfagan a la demanda se denomina Routing and Spectrum Allocation Problem (RSA), y ha recibido mucho inter ́es en los u ́ltimos an ̃os. Formalmente, dado un grafo G = (V,E) que representa la red de fibra ́optica, un conjunto de demandas D = {(si,ti,vi)}ki=1 ?de modo tal que cada demanda i ∈ {1,...,k} tiene un origensi ∈V,undestinoti ∈V yunvolumenvi ∈Z+?yunacantidads∈Z+ de slots disponibles, el RSA consiste en asignar un lightpath a cada demanda, de modo tal que los lightpaths no se superpongan. En otras palabras, a cada demanda i ∈ {1,...,k} se le debe asignar un camino entre si y ti en G y un intervalo de vi slots consecutivos en [0,s], de modo tal que si dos demandas utilizan una misma arista para sus caminos, entonces los intervalos de slots que recibieron deben ser disjuntos.En el presente trabajo se proponen varios modelos de programaci ́on lineal entera para este problema, compar ́andose su efectividad sobre instancias de la literatura. Se presentan diversas t ́ecnicas de modelado, y se estudia en particu- lar un mecanismo para formular conjuntos de unos consecutivos en vectores de variables binarias. El prop ́osito de este trabajo es desarrollar una base sobre la cual se pueda comenzar un estudio poliedral del RSA, con el objetivo final de resolver en forma exacta instancias reales.