Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resumen
Un algoritmo Branch & Cut para un problema de asignación de
frecuencias en redes de telefonía celular
Modelado del problema
Conceptos básicos
Estudio Poliedral
Branch & Cut
Resultados computacionales
Introducción al problema
Modelos de PLE
Conclusiones y trabajo futuro
Tesis de Licenciatura de Diego Delle Donne
Director: Dr. Javier Marenco
Departamento de Computación, FCEN, Universidad de Buenos Aires.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Introducción al problema
Redes de telefonía celular: ¿Cómo funcionan las comunicaciones?
Hand-over
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Introducción al problema
Posibles problemas:
Co-canalización (mismo canal)
Interferencia por canales adyacentes
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Introducción al problema
Tendido de una red para cubrir una zona:
… pero la cantidad de canales disponibles es muy limitada…
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Introducción al problema
Objetivos de una asignación de frecuencias:
1. Asignar un canal a cada antena de manera tal que no se produzcan co-canalidades.
2. Minimizar la interferencia generada por canales adyacentes en las antenas.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Introducción al problema
Consideraciones:
Antenas habituales de 120 grados y más de una por sector
Canales de control (BCCH) Vs. canales de transferencia (TCH)
Problema muy estudiado heurísticamente pero muy poco estudiado de manera exacta.
Omitimos otras características del problema: Canales bloqueados, distancias mínimas, etc.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Modelado del problema
Introducción al problema
Conceptos básicos
Modelos de PLE
Estudio poliedral
Branch & Cut
Resultados computacionales
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Modelado del problema
G = (V, E)
C = {c1, c2, … , ct}
Objetivo: Colorear G usando colores de C, de manera tal que el coloreo minimice la cantidad de vértices adyacentes que reciben colores adyacentes (NP-H).
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
Modelado del problema
Modelos de PLE
Estudio poliedral
Branch & Cut
Nuevos resultados
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
Programación lineal
Hallar que maximice { ctx / Ax ≤ b }
Ejemplo: x = (x1,x2)
Maximizar x1 + x2
x1 + 3 x2 ≤ 12
3 x1 + 4 x2 ≤ 20
x1, x2 ≥ 0
Sujeto a
nx
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
x1
x2
Maximizar x1 + x2
x1 + 3 x2 ≤ 12
3 x1 + 4 x2 ≤ 20
x1, x2 ≥ 0
Sujeto a
2
12+1 = 3
1
2 1+2 = 3
x1+x2 = 3
x1+x2 = 5
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
x1
x2
Maximizar x1 + x2
x1 + 3 x2 ≤ 12
3 x1 + 4 x2 ≤ 20
x1, x2 ≥ 0
Sujeto a
16/5
12/5x1+x2 = 28/5
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
Programación lineal entera
Hallar que maximice { ctx / Ax ≤ b }nx
x1
x2
Planos de corte
x1+x2 = 5
1 2 3 4
1
2
3
4
5
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
Programación lineal entera
Branch & Bound
x1
x2
x2 ≥ 3
x2 ≤ 2
Branch & Cut = Branch & Bound + Planos de corte
1 2 3 4
1
2
3
4
5
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conceptos básicos
Complejidad
Programación lineal P
Programación lineal entera NP-C
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Modelos de PLE
Conceptos básicos
Estudio poliedral
Branch & Cut
Resultados computacionales
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Modelos de PLE
Modelos considerados:
Orientation model (Grötschel et. al., 1998)
Distance model
Representatives model (Campêlo, Corrêa y Frota, 2004)
Stable model (Méndez Díaz y Zabala, 2001)
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Modelos de PLE: Stable model
1vcc C
x
v V
xvc indica si el vértice v está pintado con el color c
zvw indica si los vértices v y w reciben colores adyacentes
min vwvw E
z
1vc wcx x , ,vw E v w c C
1 21 vc wc vwx x z ,vw E v w
1 2 1 2,| - | 1c c C c c
{0,1}vcx , v V c C {0,1}vwz ,vw E v w
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Estudio poliedral
Modelos de PLE
Branch & Cut
Resultados computacionales
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: La 3-Colors Inner Clique Inequality es válida para
PS(G,C) y, si |C| > y |C| > |K| + 4, además define facetas de
PS(G,C).
Definición: Sea una clique de G y un vértice de la
clique. Sea un conjunto de colores consecutivos.
Definimos la 3-Colors Inner Clique Inequality como:
Estudio poliedral
Q = {c1, c2, c3}
K V k K
1 2 3}Q {c ,c ,c
1 2 3 2 ( ) 1vk kc kc kc vc
v K v Kv k v k
z x x x x
k
( )G
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: La 3-Colors Outer Clique Inequality es válida para
PS(G,C) y, si |C| > y |C| > |K| + 4, además define facetas de
PS(G,C).
Definición: Sea una clique de G y un vértice de la
clique. Sea un conjunto de colores consecutivos.
Definimos la 3-Colors Outer Clique Inequality como:
Estudio poliedral
Q = {c1, c2, c3}
K V k K
1 2 3}Q {c ,c ,c
1 2 3 1 3 ( 2 ) ( ) 2vk kc kc kc vc vc
v K v Kv k v k
z x x x x x
k
( )G
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: La 4-Colors Vertex Clique Inequality es válida para
PS(G,C) y, si |C| > y |C| > |K| + 4, además define facetas de
PS(G,C).
Definición: Sea una clique de G y un vértice de la
clique. Sea un conjunto de colores consecutivos.
Definimos la 4-Colors Vertex Clique Inequality como:
Estudio poliedral
Q = {c1, c2, c3 ,c4}
K V k K
1 2 3 4}Q {c ,c ,c ,c
1 2 3 4 2 3( 2 2 ) ( ) 2vk kc kc kc kc vc vc
v K v Kv k v k
z x x x x x x
k
( )G
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: La Consecutive Colors Clique Inequality es válida
para PS(G,C) y, si |C| > , |C|>|Q|, |C|>|K|+4, |K|> y |
C| > 2|K|-|Q|+2, además define facetas de PS(G,C).
Definición: Sea una clique de G y Q = {c1,…,cq} un conjunto
de colores consecutivos. Definimos la Consecutive Colors Clique
Inequality como:
Estudio poliedral
Q =
K V
1
1
,,
2 ( - 1) +q
q
vc vc vc vwv K c Q v w K
c c c
x x x q z
c1 cqc2 ……x x x x x x x
q-1 adyacencias
Resta 2 adyacencias
Resta 1 adyacencia
( )G2
|Q|
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: La Multi Consecutive Colors Clique Inequality es válida
para PS(G,C).
Definición: Sea una clique de G y ,
Estudio poliedral
C =
K V
1
1
1 1 ,,
2 ( - 1) +h hqh h
h hqh
p p
vc h vwvc vch v K h v w Kc Q
c c c
x x x q z
1
1 1 11{ ,..., }qQ c c
p conjuntos no adyacentes de
colores consecutivos. Definimos la Multi Consecutive Colors Clique
Inequality como:
2
2 2 21 1{ ,..., },..., { ,..., }
p
p p pq qQ c c Q c c
1Q 2Q pQ
…
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Teorema: Las Clique Inequalities son válidas para PS(G,C) y, si K
es una clique maximal y |C| > , entonces también definen
facetas de PS(G,C).
Definición: Sea una clique de G y un color
disponible. Definimos la Clique Inequality (Méndez Díaz y Zabala,
2001) como:
Estudio poliedral
K V c C
1vcv K
x
( )G
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut
Estudio poliedral
Resultados computacionales
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut
Planos de corte: Algoritmos de separación
Técnicas usadas:
Cotas primales: Redondeo de soluciones
Reducción de subproblemas por implicaciones lógicas
Selección de variable para el branch
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Algoritmos de separación
Dada una solución fraccional y* = (x*,z*), buscamos cliques que violen la 3CIK Inequality:
1 2 3 2 ( ) 1vk kc kc kc vc
v K v Kv k v k
z x x x x
2
* *( )k vc vkv x z
Elegimos un vértice k y definimos el peso de un vértice v adyacente a k como:
El objetivo ahora es encontrar una clique K N(k) de manera tal que
1 2 3
* * *( ) 1 ( )k kc kc kcv K
v x x x
valor a superar
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Algoritmos de separación
Sea N(k) = {v1, v2, … , vp} tal que vi vi+1 i = 1,…,p-1 )ω()ω( Búsqueda por Backtracking:
v1
v2
…
vp
<maxω ω maxω
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Algoritmos de separación
Sea N(k) = {v1, v2, … , vp} tal que vi vi+1 i = 1,…,p-1 )ω()ω( Búsqueda por Backtracking:
Conjunto de vértices y pesos de los mismos
Adyacencias entre los vértices
Qué cliques devolver: N primeras, N mejores, todas.
Límite de nodos del árbol a inspeccionar.
Valor a superar por el peso de las cliques
Lista de cliques que violan la restricción, ordenada por los pesos de las cliques en forma decreciente
Datos de entrada:
Parametrización:
Salida:
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
K = {v1}
para i = 2 hasta p
si K U {vi} es una clique
K = K U {vi}
fin para
si K supera el valor a superar
devolver K
si no
devolver {}
Datos de entrada:
Conjunto de vértices y pesos de los mismos
Adyacencias entre los vértices
Parametrización:
Cantidad de cliques a devolver (una para cada vi inicial)
Valor a superar por el peso de las cliques
Salida:
Lista de cliques que violan la restricción, ordenada por los pesos de las cliques en forma decreciente
Branch & Cut: Algoritmos de separación
Sea N(k) = {v1, v2, … , vp} tal que vi vi+1 i = 1,…,p-1 )ω()ω( Búsqueda por heurística golosa:
)ω(
Algoritmo:
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
)x2x(x2(v) *kc
*kc
*kc
Kvk 321
ω
Branch & Cut: Algoritmos de separación
Podemos ahora utilizar los mismos métodos de separación para la 3COK Inequality:
Al igual que antes, elegimos un vértice k y en este caso definimos el peso de un vértice v adyacente a k como:
El objetivo ahora es encontrar una clique K N(k) de manera tal que
valor a superar
1 2 3 1 3 ( 2 ) ( ) 2vk kc kc kc vc vc
v K v Kv k v k
z x x x x x
*vk
*vc
*vck z )x(x(v)
31ω
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
)x2x2x(x2(v) *kc
*kc
*kc
*kc
Kvk 4321
ω
Branch & Cut: Algoritmos de separación
Repetimos el mismo procedimiento de separación para la 4CVK Inequality:
En este caso el peso de cada vértice v adyacente a k se deine como:
Y el objetivo ahora es, nuevamente, encontrar una clique K N(k) de manera tal que
valor a superar
*vk
*vc
*vck z )x(x(v)
32ω
1 2 3 4 2 3( 2 2 ) ( ) 2vk kc kc kc kc vc vc
v K v Kv k v k
z x x x x x x
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Algoritmos de separación
Veamos ahora el caso de la CCK Inequality:
No podemos definir el peso de un vértice sin especificar antes K!
1
1
,,
2 ( - 1) +q
q
vc vc vc vwv K c Q v w K
c c c
x x x q z
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Dado Q={c1, … , cq}, definimos el “peso estimado” de cada vértice v V como:
Branch & Cut: Algoritmos de separación
Veamos ahora el caso de la CCK Inequality:
q1
q1
c,ccQc
*vc
*vc
*vcQ 2xxx(v)ω~
1
1
,,
2 ( - 1) +q
q
vc vc vc vwv K c Q v w K
c c c
x x x q z
Y usamos estos pesos para ordenar los vértices en un algoritmo similar al explicado (tanto en el backtracking como en la heurística), pero en el cual el valor a superar depende de los vértices utilizados en la clique.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Algoritmos de separación
Extendiendo intervalos para la MCCK Inequality:
1
1
1 1 ,,
2 ( - 1) +h hqh h
h hqh
p p
vc h vwvc vch v K h v w Kc Q
c c c
x x x q z
1Q
C =21c 2
q2c
2Q
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Redondeo de soluciones
Cotas primales: Redondeo de soluciones
Algoritmo:
mientras queden xvc fraccionarias
elegir (v,c) tal que xvc = max{xvc : 0 < xvc < 1}
fijar xvc = 1
fijar xvc’ = 0 para todo c’ c
fijar xwc = 0 para todo w, vw E
fin mientras
Si para todo v
solución encontrada
1vcc C
x
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Implicaciones lógicas
Reducción de subproblemas por implicaciones lógicas:
Algoritmo:
Si
fijar para todo c’ c
fijar para todo w, vw E
Si y para vw E
fijar si
fijar si no
1vcx
' 0vcx
0wcx
11vcx
21wcx
1 2| | 1c c 1vwz
0vwz
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Branch & Cut: Selección de variable de branch
Selección de variable para branch:
Se elige la variable xvc cuyo valor esté más cercano a 0.5
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Branch & Cut
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Instancias de prueba extraídas del proyecto EUCLID CALMA.
Conjunto de prueba de 30 instancias (escogidas de la experimentación preliminar)
Pentium IV con 1Gb de memoria RAM y un microprocesador de 1.8 Ghz.
Contexto:
Las familias de desigualdades parecen no funcionar muy bien cuando se las utiliza por separado.
La combinación de las desigualdades MCCK y K brindan una fuerte fase de planos de corte para el branch & cut
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Este gráfico muestra los tiempos de ejecución promedio para diferentes combinaciones de familias utilizando como base la combinación MCCK+K.
También se muestra el tipo de separación utilizada para buscar las cliques.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Visualizando en detalle los tiempos obtenidos por el backtracking podemos ver que la mejor combinación para este conjunto de pruebas resulta ser la combinación base (MCCK+K), utilizando el criterio “best” para la búsqueda de cliques.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Luego se testearon diferentes valores para la cantidad de cliques devueltas por el backtracking (con MCCK+K y devolviendo las “mejores” cliques).
También se muestra el límite de nodos para la exploración del árbol de backtracking: 150, 300, 450 y 600 nodos.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Analizando en detalle nuevamente podemos ver que los mejores tiempos se obtienen usando un número entre 14 y 22 cliques (en particular el mejor caso se obtuvo usando 20 cliques) con un límite de 150 nodos.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Finalmente se experimentó con diferentes valores la cantidad de rondas de cortes utilizadas durante las fases de planos de cortes.
A su vez, se varía el skip factor con valores entre 1 y 5.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
En este caso, viendo en detalle, se nota que la diferencia entre los valores para el skip factor utilizando infinitas rondas es despreciable, aunque para los demás valores de rondas no lo es.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
El agregado de las demás familias a la combinación base de MCCK+K sólo empeora los tiempos de resolución.
Resultados:
La mejor elección de parámetros para el Branch & Cut se logra utilizando el backtracking con un límite de 150 nodos en la exploración del árbol de bactracking y devolviendo las mejores 20 cliques halladas. Además de un skip factor de 1 y la utilización de infinitas rondas de cortes.
Ahora con esta combinación de desigualdades válidas y la mejor parametrización hallada comparamos los tiempos obtenidos contra la ejecución de CPLEX sobre el modelo original.
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Resultados computacionales
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conclusiones y trabajo futuro
Resultados computacionales
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conclusiones y trabajo futuro
El poliedro asociado al problema tiene una estructura combinatoria muy interesante.
El Branch & Cut parece ser muy eficiente y las desigualdades válidas propuestas parecen ayudar en forma decisiva.
La experimentación muestra que la combinación “MCCK+K+best 20” parece ser la mejor parametrización para el algoritmo branch & cut.
Conclusiones:
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
Conclusiones y trabajo futuro
Profundizar el estudio sobre los otros modelos.
Incorporar a este modelo los aspectos dejados de lado al comienzo.
Trabajo Futuro:
Adaptar el algoritmo para intentar la resolución de instancias más grandes.
Conclusiones y trabajo futuro
Un algoritmo Branch & Cut para un problema de asignación de frecuencias en redes de telefonía
celular
¡¡Muchas gracias!!
Diego Delle Donne
Departamento de Computación, FCEN, Universidad de Buenos Aires.