El problema del m´aximo cubrimiento ordenadoelena/PagWebOptimos/Presentaci...El problema del...

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 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



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.




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).




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




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




(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




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∑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



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)




i−1∑i ′=1

n∑j=k+1

ai ′j ≤ (i − 1)(1−k∑

j=i

aij) ∀i = 2, . . . , n, k ≥ i (3)




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)




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)




aij +n∑

k=i−1k 6=j−1

ai−1,k ≤ 1 ∀i ≥ 2, j ≥ i (6)




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).




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





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


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


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




Gracias por la atencion


El problema del m´aximo cubrimiento ordenadoelena/PagWebOptimos/Presentaci...El problema del...

Documents

Transcript of El problema del m´aximo cubrimiento ordenadoelena/PagWebOptimos/Presentaci...El problema del...