Tecnicas de DescomposicionModelos Determinsticos en Investigacion de Operaciones
Dott.ssa Rosa Medina
Universidad de Concepcion
16 de junio de 2015
1Tecnicas de Descomposicion R. Medina
Ejemplo: Adquisicion de gas y carbon para dos anos
Minimizar los costos de adquisicion Satisfaccion de la demanda del primer ano y de segundo ano Restricciones de abastecimiento equilibrado
Variables de decision:c0: compra de carbon el primer anog0: compra de gas el primer anoc1: compra de carbon el segundo ano con demanda altag1: compra de gas el segundo ano con demanda altac2: compra de carbon el segundo ano con demanda mediag2: compra de gas el segundo ano con demanda mediac3: compra de carbon el segundo ano con demanda bajag3: compra de gas el segundo ano con demanda baja
2Tecnicas de Descomposicion R. Medina
Ejemplo: Adquisicion de gas y carbon para dos anos
Min 4.5c0 +5.1g0 +0.3(7.5c1 +8.5g1) +0.5(6c2 +5.5g2) +0.2(3c3 +4g3)s. a c0 +g0 750
c0 +g0 +c1 +g1 =1650c0 +c1 1100c0 +c1 550
g0 +g1 1100g0 +g1 550
c0 +g0 +c2 +g2 =1500c0 +c2 1000c0 +c2 500
g0 +g2 1000g0 +g2 500
c0 +g0 +c3 +g3 =1300c0 +c3 866c0 +c3 433
g0 +g3 866g0 +g3 433
c0 0 g0 0 c1 0 g1 0 c2 0 g2 0 c3 0 g3 0
3Tecnicas de Descomposicion R. Medina
Ejemplo: Adquisicion de gas y carbon para dos anos
Min 4.5c0 +5.1g0 +0.3(7.5c1 +8.5g1) +0.5(6c2 +5.5g2) +0.2(3c3 +4g3)s. a c0 +g0 750
c0 +g0 +c1 +g1 =1650c0 +c1 1100c0 +c1 550
g0 +g1 1100g0 +g1 550
c0 +g0 +c2 +g2 =1500c0 +c2 1000c0 +c2 500
g0 +g2 1000g0 +g2 500
c0 +g0 +c3 +g3 =1300c0 +c3 866c0 +c3 433
g0 +g3 866g0 +g3 433
c0 0 g0 0 c1 0 g1 0 c2 0 g2 0 c3 0 g3 0
4Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Min cx
s.a Ax = b
x X = {x : Dx d , x 0}
X es un poliedro.
5Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
variables duales
Min cx
s.a Ax = b w
x X = {x : Dx d , x 0} v
6Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
problema dual
Max wb +vd
s.a wA +vD cw irrestricto, v 0
7Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Supongamos que cuando w esta fijo, el problema con las variablesv es facil de resolver.
Max wb +vd
s.a wA +vD cw irrestricto, v 0
8Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Podemos descomponer el problema:
Maxw irrestricto
wb +max vd
s.a vD c wAv 0
9Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Dualizamos el problema interior:
Maxw irrestricto
{wb +min (c wA)x
s.a x X}
El optimo de este problema se encuentra en uno de los puntosextremos x del poliedro X .
10Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Sea z el valor optimo de la funcion objetivo. Podemos escribir elproblema en funcion de los puntos extremos x como:
Max z
s.a z wb + (c wA)xj j = 1, . . . , kz,w irrestrictos
11Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Problema Maestro
Max z
s.a z wb + (c wA)xj j = 1, . . . , kz,w irrestrictos
k puede ser muy grande. Podemos relajar algunas restricciones yobtener una solucion optima (z , w) para el problema relajado (cotasuperior).Podemos verificar si la solucion no viola alguna de las restriccionesrelajadas. Si las viola, agregamos las restricciones violadas eiteramos. Si no las viola, la solucion es optima.
12Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
como encontramos las restricciones violadas?
13Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Una restriccion esta violada si, para algun xj :
z > wb + (c wA)xj
14Tecnicas de Descomposicion R. Medina
Descomposicion de Benders
Podemos encontrar la restriccion mas violada resolviendo:
wb+ min{(c wA)x}x X
Subproblema de Benders
15Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Max 2w1 +3w2 +2v1 +5v2 +2v3 +6v4s. a w1 +w2 +v1 +v2 -2
w2 +2v2 -1w1 -v3 +2v4 -1
2w2 +v3 +v4 1w1 0 w2 0 v1 0 v2 0 v3 0 v4 0
16Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Max 2w1 +3w2 +2v1 +5v2 +2v3 +6v4s. a w1 +w2 +v1 +v2 -2
w2 +2v2 -1w1 -v3 +2v4 -1
2w2 +v3 +v4 1w1 0 w2 0 v1 0 v2 0 v3 0 v4 0
17Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Max 2w1 +3w2 + Max 2v1 +5v2 +2v3 +6v4s. a s. a v1 +v2 -2-w1-w2
2v2 -1-w2-v3 +2v4 -1-w1v3 +v4 1-2w2
w1 0 w2 0 v1 0 v2 0 v3 0 v4 0
18Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Variables duales
Max 2w1 +3w2 + Max 2v1 +5v2 +2v3 +6v4s. a s. a v1 +v2 -2-w1-w2 x1
2v2 -1-w2 x2-v3 +2v4 -1-w1 x3v3 +v4 1-2w2 x4
w1 0 w2 0 v1 0 v2 0 v3 0 v4 0
19Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Max 2w1 +3w2 + Min (-2-w1-w2)x1 +(-1-w2)x2 +(-1-w1)x3 +(1-w2)x4s. a s. a x1 2
x1 +2x2 5-x3 +x4 22x3 +x4 6
w1 0 w2 0 x1 0 x2 0 x3 0 x4 0
20Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
Problema Maestro de Benders
Max z
s.a z 2w1 + 3w2 + (2 w1 w2)x j1 + (1 w2)xj2 + (1 w1)x
j3 + (1 2w2)x
j4 j = 1, . . . , k
z irrestricto,w 0
21Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de BendersSubproblema de Benders
2w1 + 3w2 + minxjX {(2 w1 w2)xj1 + (1 w2)x
j2 + (1 w1)x
j3 + (1 2w2)x
j4}
x1
x2
x3
x4
22Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro:
23Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)
Problema Maestro:
Max zs.a z 2w1 3w2 0
z irr w1 0 w2 0
24Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema: wb+min(c-wA)x2, x2 X
25Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema:
26Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema:
2w1 + 3w2 +min(x21,x2
2)X1{(2 w1 w2)x21 + (1 w2)x22} +min(x2
3,x2
4)X2{(1 w1)x23 + (1 2w2)x24}
27Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema:
0 +min(x21,x2
2)X1{2x21 x22}
x1
x2
+min(x2
3,x2
4)X2{x23 + x24}
x3
x4
28Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema:
0 +min(x21,x2
2)X1{2x21 x22}
x1
x2
(x21 , x22 ) = (2,
32
)
+min(x2
3,x2
4)X2{x23 + x24}
x3
x4
(x23 , x24 ) = (3, 0)
29Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema: x2 = (2, 32 , 3, 0)Restriccion violada:
z > wb + (c wA)xj?
30Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema: x2 = (2, 32 , 3, 0)Restriccion violada:
z > wb + (c wA)xj?0 > 172 ? restriccion violada
agregar restriccionz 2w1 + 3w2 + (2 w1 w2)x21 + (1 w2)x22 + (1 w1)x23 + (1 2w2)x24
z 3w1 12w2 172
31Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro:
32Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)
Problema Maestro:
Max zs.a z 2w1 3w2 0
z +3w1 +12w2 172
z irr w1 0 w2 0
33Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro: (z , w1, w2) = (
175 ,1710 , 0)
Subproblema:2w1 + 3w2 +min(x3
1,x3
2)X1{(2 w1 w2)x31 + (1 w2)x32} +min(x3
3,x3
4)X2{(1 w1)x33 + (1 2w2)x34}
34Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro: (z , w1, w2) = (
175 ,1710 , 0)
Subproblema:17
5+min
(x31,x3
2)X1{3
10x31 x32}
x1
x2
(x31 , x32 ) = (0,
52
)
+min(x3
3,x3
4)X2{ 7
10x33 + x
34}
x3
x4
(x33 , x34 ) = (0, 0)
35Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro: (z , w1, w2) = (
175 ,1710 , 0)
Subproblema:x3 = (0, 52 , 0, 0)Restriccion violada:
z > wb + (c wA)xj?
36Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro: (z , w1, w2) = (
175 ,1710 , 0)
Subproblema:x3 = (0, 52 , 0, 0)Restriccion violada:
z > wb + (c wA)xj?175 >
5910 ? restriccion violada agregar restriccion
z 2w1 + 3w2 + (2 w1 w2)x31 + (1 w2)x32 + (1 w1)x33 + (1 2w2)x34z 2w1 + 12w2 52
37Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)Problema Maestro:
38Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)
Problema Maestro:
Max zs.a z 2w1 3w2 0
z +3w1 +12w2 172
z 2w1 12w2 52z irr w1 0 w2 0
39Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)Problema Maestro: (z , w1, w2) = (
4910 ,
65 , 0)
Subproblema:2w1 + 3w2 +min(x4
1,x4
2)X1{(2 w1 w2)x41 + (1 w2)x42} +min(x4
3,x4
4)X2{(1 w1)x43 + (1 2w2)x44}
40Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)Problema Maestro: (z , w1, w2) = (
4910 ,
65 , 0)
Subproblema:12
5+min
(x41,x4
2)X1{4
5x41 x42}
x1
x2
+min(x4
3,x4
4)X2{ 1
5x43 + x
44}
x3
x4
41Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)Problema Maestro: (z , w1, w2) = (
4910 ,
65 , 0)
Subproblema:12
5+min
(x41,x4
2)X1{4
5x41 x42}
x1
x2
(x41 , x42 ) = (2,
32
)
+min(x4
3,x4
4)X2{ 1
5x43 + x
44}
x3
x4
(x43 , x44 ) = (0, 0)
42Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0)Problema Maestro: (z , w1, w2) = (
4910 ,
65 , 0)
Subproblema:x4 = (2, 32 , 0, 0)Restriccion violada:
z > wb + (c wA)xj?4910 >
5510 ? restriccion violada agregar restriccion
z 2w1 + 3w2 + (2 w1 w2)x41 + (1 w2)x42 + (1 w1)x43 + (1 2w2)x44z 1
2w2 112
43Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro:
44Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro:
Max zs.a z 2w1 3w2 0
z +3w1 +12w2 172
z 2w1 12w2 52z + 12w2 112
z irr w1 0 w2 0
45Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro: (z , w1, w2) = (5,1,1)Subproblema:
2w1 + 3w2 +min(x51,x5
2)X1{(2 w1 w2)x51 + (1 w2)x52} +min(x5
3,x5
4)X2{(1 w1)x53 + (1 2w2)x54}
46Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro: (z , w1, w2) = (5,1,1)Subproblema:
-5 +min(x51,x5
2)X1{0x51 + 0x52}
x1
x2
+min(x5
3,x5
4)X2{0x53 + 3x54}
x3
x4
47Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro: (z , w1, w2) = (5,1,1)Subproblema:
-5 +min(x51,x5
2)X1{0x51 + 0x52}
x1
x2
(x51 , x52 ) = (0, 0)
+min(x5
3,x5
4)X2{0x53 + 3x54}
x3
x4
(x53 , x54 ) = (0, 0)
48Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro: (z , w1, w2) = (5,1,1)Subproblema:x5 = (0, 0, 0, 0)Restriccion violada:
z > wb + (c wA)xj?5 > 5? restriccion no violada
Cual es el valor de (w1,w2, v1, v2, v3, v4)?
49Tecnicas de Descomposicion R. Medina
Ejemplo: Descomposicion de Benders
iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x
3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)
Problema Maestro: (z , w1, w2) = (5,1,1)Subproblema:x5 = (0, 0, 0, 0)Restriccion violada:
z > wb + (c wA)xj?5 > 5? restriccion no violada
Cual es el valor de (w1,w2, v1, v2, v3, v4)?(w1,w2, v1, v2, v3, v4) = (1,1, 0, 0, 0, 0)
50Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
Problema Maestro de Benders
Max z
s.a z wb + (c wA)xj j = 1, . . . , kz , w irrestrictos
51Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
Variables duales
Max z
s.a z wb + (c wA)xj j = 1, . . . , k jz irrestricto
52Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
Problema dual
Mink
j=1(wb + (c wA)xj)js.a
kj=1 j = 1
j 0 j = 1, . . . , k
53Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
Agrupamos en funcion de w
Mink
j=1 cxjj + w(k
j=1 jb k
j=1 Axjj)
s.ak
j=1 j = 1
j 0 j = 1, . . . , k
54Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
Agrupamos en funcion de w
Mink
j=1 cxjj + w(kj=1
jb kj=1
Axjj)
s.ak
j=1 j = 1
j 0 j = 1, . . . , k
w son multiplicadores de Lagrange (w irrestrictos)
55Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
El problema original es
Mink
j=1 cxjj
s.ak
j=1 Axjj =k
j=1 jbkj=1 j = 1
j 0 j = 1, . . . , k
56Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
... comok
j=1 j = 1
Mink
j=1 cxjj
s.ak
j=1 Axjj = bkj=1 j = 1
j 0 j = 1, . . . , k
corresponde a la descomposicion de Dantzing-Wolfe
57Tecnicas de Descomposicion R. Medina
Relacion entre las Tecnicas de Descomposicion
El problema original es:
Min cx
s.a Ax = b
x X
58Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema original
Min cx
s.a Ax bx X
muchas restricciones
59Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema original
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, bProblema reducido
Min cx
s.a Ax bx X
60Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
61Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
Nota: cx es una cota inferior para el problema original
62Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
3 Si x satisface todas las restricciones del problema original,entonces es la solucion optima.
63Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
3 Si x satisface todas las restricciones del problema original,entonces es la solucion optima.
4 Sino, tenemos que agregar restricciones violadas a A, b eiterar.
64Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto derestricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
3 Si x satisface todas las restricciones del problema original,entonces es la solucion optima.
4 Sino, tenemos que agregar restricciones violadas a A, b eiterar.
Como encontramos restricciones violadas?65
Tecnicas de Descomposicion R. Medina
Modelos con muchas restricciones y el problema deseparacion
Problema reducido
Min cx
s.a Ax bx X
1 Inicializar un problema reducido con un subconjunto de restricciones A, b
2 Resolver el problema reducido y obtener la solucion optima x
3 Si x satisface todas las restricciones del problema original, entonces es la solucion optima.
4 Sino, tenemos que agregar restricciones violadas a A, b e iterar.
Como encontramos restricciones violadas? Resolviendo unproblema de separacion
66Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set): Dado ungrafo no orientado G = (V ,E ) con peso pj en cada vertice j V ,n = |V | y m = |E |.
67Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set): Dado ungrafo no orientado G = (V ,E ) con peso pj en cada vertice j V ,n = |V | y m = |E |.Un conjunto independiente de vertices de G es un subconjunto denodos S V , tal que E (S) = (ningun arco en E une los nodosen S).
68Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set): Dado ungrafo no orientado G = (V ,E ) con peso pj en cada vertice j V ,n = |V | y m = |E |.Un conjunto independiente de vertices de G es un subconjunto denodos S V , tal que E (S) = (ningun arco en E une los nodosen S).El problema determina un conjunto independiente de vertices de Gcon peso maximo.
69Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):
xj =
{1 si el vertice j pertenece a S
0 e.o.c.
Max
jV pjxjs.a xi + xj 1 (i , j) E
xj {0, 1}j V
70Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Una formulacion alternativa se basa en el concepto de clique. Unaclique es un subconjunto k de vertices de V , k V , tal queE (k) = {(i , j) : i , j k}, es decir, todos los pares de vertices en ktienen un arco en E que los une (subgrafo completo).Una clique se dice maximal si no hay otra clique que la contenga(no existe un vertice en V /k unido a algun vertice de k por unarco en E ).
71Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):
Max
jV pjxjs.a
jk xj 1 k K
xj {0, 1}j V
Donde K es el conjunto de cliques maximales.
72Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):El problema restringido, considera algunas cliques k K .
El problema de separacion consiste en determinar una clique k talque:
jkxj > 1
dada la solucion x para el problema restringido.Para determinar la clique utilizamos el conjunto independiente devertices en el grafo complemento restringido a las variables queestan en la solucion.
73Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Dado el grafo G = (V ,E ) con V = {1, 2, 3, 4, 5, 6} con pesos{5, 4, 2, 4, 3, 1}, yE = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 5), (2, 6), (5, 6)}.
74Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Dado el grafo G = (V ,E ) con V = {1, 2, 3, 4, 5, 6} con pesos{5, 4, 2, 4, 3, 1}, yE = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 5), (2, 6), (5, 6)}.Obtenemos K = {{1, 2, 5, 6}, {1, 3}, {1, 4}}
75Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Dado el grafo G = (V ,E ) con V = {1, 2, 3, 4, 5, 6} con pesos{5, 4, 2, 4, 3, 1}, yE = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 5), (2, 6), (5, 6)}.Obtenemos K = {{1, 2, 5, 6}, {1, 3}, {1, 4}}El modelo explcito sera:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 +x3 1x1 +x4 1
x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
76Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 1:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion:
77Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 1:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4, x5, x6) = (1, 0, 1, 1, 0, 0) con valor 11Problema de separacion:
78Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 1:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4, x5, x6) = (1, 0, 1, 1, 0, 0) con valor 11Problema de separacion:
Max y1 +y3 +y4s.a y3 +y4 1
y1 {0, 1} y3 {0, 1} y4 {0, 1}
79Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 1:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4) = (1, 0, 1, 1, 0, 0) con valor 11Problema de separacion:
Max y1 +y3 +y4s.a y3 +y4 1
y1 {0, 1} y3 {0, 1} y4 {0, 1}
Solucion: (y1, y2, y3, y4, y5, y6) = (1, 0, 1, 0, 0, 0) con valor 22 > 1? restriccion violadaAgregar x1 + x3 1
80Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 2:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion:
81Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 2:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4, x5, x6) = (0, 1, 1, 1, 0, 0) con valor 10Problema de separacion:
82Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 2:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4, x5, x6) = (0, 1, 1, 1, 0, 0) con valor 10Problema de separacion:
Max y2 +y3 +y4s.a y2 +y3 1
y3 +y4 1y2 +y4 1
y2 {0, 1} y3 {0, 1} y4 {0, 1}
83Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas restricciones y el problemade separacion
Conjunto Independiente de Vertices (Stable Set):Iteracion 2:Problema reducido:
Max 5x1 +4x2 +2x3 +4x4 +3x5 +x6s.a x1 +x2 +x5 +x6 1
x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}
Solucion: (x1, x2, x3, x4, x5, x6) = (0, 1, 1, 1, 0, 0) con valor 10Problema de separacion:
Max y2 +y3 +y4s.a y2 +y3 1
y3 +y4 1y2 +y4 1
y2 {0, 1} y3 {0, 1} y4 {0, 1}
Solucion: (y1, y2, y3, y4, y5, y6) = (0, 1, 0, 0, 0, 0) con valor 11 > 1? restriccion no violada solucion optima84
Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasPrimal
Min cx
s.a Ax bx 0
Dual
Max by
s.a Ay cy 0
85Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasPrimalMuchas variables
Min cx
s.a Ax bx 0
DualMuchas restricciones
Max by
s.a Ay cy 0
1 Inicializar el problema reducido con un subconjunto devariables x , A, cProblema reducido
Min cx
s.a Ax bx 0
86Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasProblema reducido
Min cx
s.a Ax bx 0
Dual del problema reducido
Max by
s.a Ay cy 0
1 Inicializar el problema reducido con un subconjunto devariables x , A, c
2 Resolver el problema reducido y obtener la solucion optima x
y la solucion dual y
87Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasProblema reducido
Min cx
s.a Ax bx 0
Dual del problema reducido
Max by
s.a Ay cy 0
1 Inicializar el problema reducido con un subconjunto devariables x , A, c
2 Resolver el problema reducido y obtener la solucion optima x
y la solucion dual y
3 Si y satisface todas las restricciones del problema dual,entonces x es la solucion optima al fijar a cero las variablesque no aparecen en el problema reducido.
88Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasProblema reducido
Min cx
s.a Ax bx 0
Dual del problema reducido
Max by
s.a Ay cy 0
1 Inicializar el problema reducido con un subconjunto devariables x , A, c
2 Resolver el problema reducido y obtener la solucion optima x
y la solucion dual y
3 Si y satisface todas las restricciones del problema dual,entonces x es la solucion optima al fijar a cero las variablesque no aparecen en el problema reducido.
4 Sino, agregar al problema reducido, las variablescorrespondientes a las restricciones violadas e iterar.
Como encontramos las variables?89
Tecnicas de Descomposicion R. Medina
Modelo con muchas variables y la generacion de columnasProblema reducido
Min cx
s.a Ax bx 0
Dual del problema reducido
Max by
s.a Ay cy 0
1 Inicializar el problema reducido con un subconjunto de variables x , A, c
2 Resolver el problema reducido y obtener la solucion optima x y la solucion dual y
3 Si y satisface todas las restricciones del problema original, entonces x es la solucion optima al fijar acero las variables que no aparecen en el problema reducido
4 Sino, agregar al problema reducido, las variables correspondientes a las restricciones violadas e iterar.
Como encontramos las variables? Resolviendo la generacion decolumnas
90Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing : Dados m objetos con pesos d1, d2, ...,dm; y ncontenedores de capacidad b, empacar cada objeto en uncontenedor de modo que no se supere la capacidad de loscontenedores y el numero de contenedores utilizados sea el mnimo.
yj =
{1 si se utiliza el contenedor j
0 e.o.c.
xij =
{1 si el objeto i va en el contenedor j
0 e.o.c.
Minn
j=1 yj
s.an
j=1 xij = 1 i = 1, . . . ,mmi=1 dixij byj j = 1, . . . , nxij {0, 1}, yj {0, 1}91
Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Supongamos que conocemos todas las posibles agrupaciones deobjetos que pueden estar simultaneamente en un contenedor.s S son los conjuntos maximales de objetos, es decir, que no sepuede agregar otro objeto sin superar la capacidad del bin.
xs =
{1 si esta en la solucion un bin con los objetos en s
0 e.o.c.
Min
sS xss.a
sS :is xs 1 i = 1, ...,mxs {0, 1}
Nota: resolvemos el relajamiento continuo92
Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Primal
Min
sS xss.a
sS :is xs 1 i = 1, ...,mxs 0
Dual
Maxm
i=1 yi
s.a
is yi 1 s Syi 0 i = 1, ...,m
s S son los conjuntos maximales de objetos, es decir, que no sepuede agregar otro objeto sin superar la capacidad del bin.S = {s {1, 2, 3, ...,m} : is di b,iS{j} di > b, j / s}
93Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Primal
Min
sS xss.a
sS :is xs 1 i = 1, ...,mxs 0
Dual
Maxm
i=1 yi
s.a
is yi 1 s Syi 0 i = 1, ...,m
Dada una solucion optima para el problema dual restringido,podemos resolver el problema de generacion de columnasencontrando un subconjunto maximal cuya suma sea mayor a unoGeneracion de columnas
Maxm
i=1 yi zi
s.am
i=1 dizi bzi {0, 1}
94Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing : Dado un conjunto de m = 5 objetos con pesod = {7, 5, 4, 4, 3} y contenedores de capacidad b = 10,consideremos las variables asociadas a una solucion inicialS = {{1, 5}, {2, 5}, {3, 5}, {4, 5}}.Iteracion 1:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5}s. a x{1,5} 1
x{2,5} 1x{3,5} 1
x{4,5} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
95Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 1:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5}s. a x{1,5} 1
x{2,5} 1x{3,5} 1
x{4,5} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
Solucion: x = (1, 1, 1, 1) y y = (1, 1, 1, 1, 0) con valor 4.
96Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 1:Solucion: x = (1, 1, 1, 1) y y = (1, 1, 1, 1, 0) con valor 4.Generacion de columnas
Max z1 +z2 +z3 +z4s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (0, 0, 1, 1, 0) con valor 21 < 2? restriccion violada.Agregamos la variable:
97Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 1:Solucion: x = (1, 1, 1, 1) y y = (1, 1, 1, 1, 0) con valor 4.Generacion de columnas
Max z1 +z2 +z3 +z4s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (0, 0, 1, 1, 0) con valor 21 < 2? restriccion violada.Agregamos la variable: x{3,4}
98Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing : Iteracion 2:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4}s. a x{1,5} 1
x{2,5} 1x{3,5} +x{3,4} 1
x{4,5} +x{3,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
99Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 2:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4}s. a x{1,5} 1
x{2,5} 1x{3,5} +x{3,4} 1
x{4,5} +x{3,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
Solucion: x = (1, 1, 0, 0, 1) y y = (1, 1, 1, 0, 0) con valor 3.
100Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 2:Solucion: x = (1, 1, 0, 0, 1) y y = (1, 1, 1, 0, 0) con valor 3.Generacion de columnas
Max z1 +z2 +z3s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (0, 1, 1, 0, 0) con valor 21 < 2? restriccion violada.Agregamos la variable:
101Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 2:Solucion: x = (1, 1, 0, 0, 1) y y = (1, 1, 1, 0, 0) con valor 3.Generacion de columnas
Max z1 +z2 +z3s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (0, 1, 1, 0, 0) con valor 21 < 2? restriccion violada.Agregamos la variable: x{2,3}
102Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing : Iteracion 3:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4} +x{2,3}s. a x{1,5} 1
x{2,5} +x{2,3} 1x{3,5} +x{3,4} +x{2,3} 1
x{4,5} +x{3,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
103Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 3:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4} +x{2,3}s. a x{1,5} 1
x{2,5} +x{2,3} 1x{3,5} +x{3,4} +x{2,3} 1
x{4,5} +x{3,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
Solucion: x = (1, 0, 0, 1, 0, 1) y y = (1, 1, 0, 1, 0) con valor 3.
104Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 3:Solucion: x = (1, 0, 0, 1, 0, 1) y y = (1, 1, 0, 1, 0) con valor 3.Generacion de columnas
Max z1 +z2 +z4s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (1, 1, 0, 1, 0) con valor 31 < 3? restriccion violada.Agregamos la variable:
105Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 3:Solucion: x = (1, 0, 0, 1, 0, 1) y y = (1, 1, 0, 1, 0) con valor 3.Generacion de columnas
Max z1 +z2 +z4s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (1, 1, 0, 1, 0) con valor 31 < 3? restriccion violada.Agregamos la variable: x{1,2,4}
106Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing : Iteracion 4:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4} +x{2,3} +x{1,2,4}s. a x{1,5} +x{1,2,4} 1
x{2,5} +x{2,3} +x{1,2,4} 1x{3,5} +x{3,4} +x{2,3} 1
x{4,5} +x{3,4} +x{1,2,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
107Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 4:Primal
Min x{1,5} +x{2,5} +x{5,5} +x{4,5} +x{3,4} +x{2,3} +x{1,2,4}s. a x{1,5} +x{1,2,4} 1
x{2,5} +x{2,3} +x{1,2,4} 1x{3,5} +x{3,4} +x{2,3} 1
x{4,5} +x{3,4} +x{1,2,4} 1x{1,5} +x{2,5} +x{3,5} +x{4,5} 1
Solucion: x = (0, 0, 1, 0, 0, 0, 1) y y = (1, 0, 1, 0, 0) con valor2.
108Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 4:Solucion: x = (0, 0, 1, 0, 0, 0, 1) y y = (1, 0, 1, 0, 0) con valor 2.Generacion de columnas
Max z1 +z3s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (1, 0, 0, 0, 0) con valor 11 < 1? restriccion no violada.Solucion optima
109Tecnicas de Descomposicion R. Medina
Ejemplo: Modelo con muchas variables y la generacion decolumnas
Bin Packing :Iteracion 4:Solucion: x = (0, 0, 1, 0, 0, 0, 1) y y = (1, 0, 1, 0, 0) con valor 2.Generacion de columnas
Max z1 +z3s. a 7z1 +5z2 +4z3 +4z4 +3z5 10
z1 {0, 1} z2 {0, 1} z3 {0, 1} z4 {0, 1} z5 {0, 1}
Solucion: z = (1, 0, 0, 0, 0) con valor 11 < 1? restriccion no violada.Solucion optima x{3,5} x{1,2,4}
110Tecnicas de Descomposicion R. Medina
Bibliografa
Conejo, A.J., Castillo, E., Minguez, R., Garcia-Bertrand, R.Decomposition Techniques in Mathematical Programming,Springer. 2006.Bazaraa, M. S., Jarvis, J. J., Sherali, H. D. Linear Programmingand Network Flows, Wiley. 2005.Benders, J. F. Partitioning procedures for solving mixed-variablesprogramming problems, Numerische Mathematik, 4, 238-252,1962.
111Tecnicas de Descomposicion R. Medina
Recommended