Post on 07-Aug-2020
El problema del maximo cubrimiento ordenado
Jorg Kalcsics1, Mercedes Landete2, Alfredo Marın3, Stefan Nickel1
1Saarland University,2Universidad Miguel Hernandez de Elche, 3Universidad de Murcia.
Madrid, 2007
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Dado un conjunto de ubicaciones demandantes de un servicio enlas que se puede instalar una planta, debemos elegir donde instalary como servir para maximizar el peso ponderado de las ubicacionescubiertas.
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Dado un conjunto de ubicaciones demandantes de un servicio enlas que se puede instalar una planta, debemos elegir donde instalary como servir para maximizar el peso ponderado de las ubicacionescubiertas. Suponemos que el radio de cubrimiento es constante.
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Dado un conjunto de ubicaciones demandantes de un servicio enlas que se puede instalar una planta, debemos elegir donde instalary como servir para maximizar el peso ponderado de las ubicacionescubiertas. Suponemos que el radio de cubrimiento es constante.
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Dado un conjunto de ubicaciones demandantes de un servicio enlas que se puede instalar una planta, debemos elegir donde instalary como servir para maximizar el peso ponderado de las ubicacionescubiertas. Suponemos que el radio de cubrimiento es constante.
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Los problemas ordenados multiplican cada variable en la funcionobjetivo por una constante de ponderacion.
max X⊂S|X |=p
n∑i=1
λi wσ(i)(X )
λ = (1, 1, . . . , 1).
λ = (0, 0, . . . , 0, 1).
λ = (µ, µ, . . . , µ, 1) (0 < µ < 1).
λ = (0, . . . , 0, 1, . . . , 1).
λ = (2, 0, . . . , 0, 1).
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
y` =
{1 si se abre una planta en la ubicacion `0 en otro caso
aij =
{1 si el i-esimo de todos los pesos es el j-esimo de los abiertos0 en otro caso
Por ejemplo, si n = 7, w1 ≤ w2 ≤ . . . ≤ w7, y se cubren lasubicaciones 1, 3,4 y 7. Entonces,
(aij) =
0 0 0 1 0 0 00 0 0 0 0 0 00 0 0 0 1 0 00 0 0 0 0 1 00 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 1
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Entonces, se cumple aij = 0 cuando j < i , es decir, cero por debajode la diagonal.Por otro lado, si r es el radio de cubrimiento, definimos Si como elconjunto de ubicaciones que cubren i :
Si = {` ∈ S : di` ≤ r} i = 1, . . . , n
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
(P) maxn∑
j=1
λj
j∑i=1
wiaij
s.an∑
j=i
aij ≤∑`∈Si
y` ∀i = 1, . . . , n
y` ≤n∑
j=i
aij ∀i ∈ C , ` ∈ S con di` ≤ r
j∑i=k
aij ≤j+1∑
i=k+1
ai,j+1 ∀k, j = 1, . . . , n − 1
n∑i=1
ain ≤ 1
m∑`=1
y` = p
aij , y` ∈ {0, 1} ∀i , j = 1, . . . , n, ` = 1, . . . ,m
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Maximizamos la suma de los pesos ordenados,∑n
j=1 λj∑j
i=1 wiaij
verificando que:
n∑j=i
aij ≤∑`∈Si
y` para todo i
Si todas las plantas que cubren a i estan cerradas, entonces laubicacion i no se sirve.
y` ≤n∑
j=i
aij para todo i ∈ C , ` ∈ S con di` ≤ r
Si la ubicacion i no se cubre, entonces todas las plantas que lecubren estan cerradas.
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
j∑i=k
aij ≤j+1∑
i=k+1
ai ,j+1 para todo j ≤ n − 1, k ≤ j
La suma parcial de una columna es mayor que la misma sumaparcial de la columna anterior.
j∑i=1
ain ≤ 1
La suma de la ultima columna es menor o igual que 1 y, por tanto,la suma de cualquier columna.
m∑`=1
y` = p
El numero de plantas abiertas es p.J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Podemos simplificar observando que:(i) La suma de las ultimascolumnas vale 1 ya que al menos se cubren p ubicaciones; (ii) Laasignacion del i-esimo peso wi , i ≤ p − 1, no puede ir a unaubicacion de entre la p − i ultimas ya que, en este caso, faltarıanubicaciones con peso menor.
j∑i=1
aij = 1 ∀j = n − p + 1, . . . , n (1)
aij = 0 ∀i = 1, . . . , p−1, j = n−p+ i +1, . . . , n (2)
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
i−1∑i ′=1
n∑j=k+1
ai ′j ≤ (i − 1)(1−k∑
j=i
aij) ∀i = 2, . . . , n, k ≥ i (3)
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
0 1 2 3 4 5 6 7
n∑k=i+1
n∑j=k
akj+n∑
j=i
(j − i)aij ≤ n−i ∀i = 1, . . . , n−1 (4)
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
7 6 5 4 3 2 1 0
n∑k=i+1
n∑j=k
akj ≥n∑
j=i
(n − j)aij ∀i = 1, . . . , n− 1 (5)
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
aij +n∑
k=i−1k 6=j−1
ai−1,k ≤ 1 ∀i ≥ 2, j ≥ i (6)
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Generamos cinco problemas con 50 clientes aleatoriamente comosigue:
1 Las coordenadas de los clientes se distribuyen de modouniforme en el cuadrado Q = ((0, 0), (10, 10)).
2 Los pesos de los clientes siguen una distribucion normal en elintervalo [10, 80].
Los ejemplos 1, 3 y 5 usan p = 3 y el resto p = 4. Ademas, todoscumplen r = 1.Consideramos dos tipos de lambda’s. El primero consiste en valoresdecrecientes no negativos, es decir, λi ≥ λi+1 ≥ 0. Para el segundogeneramos valores de una uniforme en (0, 1).
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Decreciente λ Aleatorio λ
Ej. 1 2 3 4 5 1 2 3 4 5Valor Obj. 637.3 844.4 276.2 298.8 164.0 368.1 476.5 244.1 320.0 128.2
LP-Rel. 637.3 892.9 324.4 384.4 246.9 376.6 486.1 251.6 325.8 138.6(P)Gap 0.0 5.7 17.5 28.6 50.5 2.3 2.0 3.0 1.8 8.1
(P) & LP-Rel. 637.3 892.9 308.7 338.4 224.9 376.6 486.1 249.9 325.8 132.9(1) y (2) Gap 0.0 5.7 11.8 13.2 37.1 2.3 2.0 2.4 1.8 3.7
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Decreciente λ Aleatorio λ
1 2 3 4 5 1 2 3 4 5
Nodos 1 35 17 27 61 13 23 17 19 19(P) y (4)Tiempo 0.6 6.5 5.1 7.6 13.4 3.4 4.5 3.9 5.1 6.5
Nodos 1 13 11 17 33 11 15 9 17 19(P), (1) y (4)Tiempo 0.6 4.1 5.4 5.6 8.1 3.1 3.8 2.7 5.8 5.3
Nodos 1 17 17 21 61 15 19 9 15 7(P), (1), (2) y (4)Tiempo 1.2 4.6 6.1 5.3 8.1 3.3 4.9 2.1 8.1 4.5
Decreciente λ Aleatorio λ
1 2 3 4 5 1 2 3 4 5
Nodos 1 25 33 29 41 7 27 3 27 21(P) y (5)Tiempo 1.5 11.1 18.0 18.3 22.3 4.8 17.1 4.1 14.5 10.3
Nodos 1 13 15 17 31 25 15 7 15 23(P), (1) y (5)Tiempo 2.2 16.1 11.9 16.0 21.2 9.0 11.4 6.6 9.9 10.6
Nodos 1 41 15 25 43 11 17 9 17 21(P), (1), (2) y (5)Tiempo 1.7 17.9 13.3 12.9 24.3 5.3 12.7 6.4 10.2 10.3
Decreciente λ Aleatorio λ
1 2 3 4 5 1 2 3 4 5
Nodos 1 19 17 31 75 11 19 7 17 17(P) y (6)Tiempo 1.9 11.1 13.5 16.9 25.9 5.4 11.2 4.1 9.0 8.7
Nodos 1 13 19 13 45 25 27 11 15 11(P), (1) y (6)Tiempo 3.0 17.8 16.3 17.2 29.7 11.3 16.2 6.9 22.4 12.0
Nodos 1 21 23 25 41 15 21 7 15 15(P), (1), (2) y (6)Tiempo 2.3 11.9 11.8 9.8 13.9 5.9 11.3 4.8 9.7 7.7
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado
El problema del maximo cubrimiento ordenado
El problemaEl modeloSimplificacionesResultados computacionales
Gracias por la atencion
J. Kalcsics, M. Landete, A. Marın, S. Nickel Maximo Cubrimiento Ordenado