3_Benders.pdf

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



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


Descomposicion de Benders

Min cx

s.a Ax = b

x X = {x : Dx d , x 0}

X es un poliedro.



variables duales

Min cx

s.a Ax = b w

x X = {x : Dx d , x 0} v



problema dual

Max wb +vd

s.a wA +vD cw irrestricto, v 0



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



Podemos descomponer el problema:

Maxw irrestricto

wb +max vd

s.a vD c wAv 0



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 .



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



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.



como encontramos las restricciones violadas?



Una restriccion esta violada si, para algun xj :

z > wb + (c wA)xj



Podemos encontrar la restriccion mas violada resolviendo:

wb+ min{(c wA)x}x X

Subproblema de Benders


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



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



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



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



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



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


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



iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro:



iteracion 1:Dado x1 = (0, 0, 0, 0)

Problema Maestro:

Max zs.a z 2w1 3w2 0

z irr w1 0 w2 0



iteracion 1:Dado x1 = (0, 0, 0, 0)Problema Maestro: (z , w1, w2) = (0,0,0)Subproblema: wb+min(c-wA)x2, x2 X



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}




0 +min(x21,x2

2)X1{2x21 x22}

x1

x2

+min(x2

3,x2

4)X2{x23 + x24}

x3

x4




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)



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?



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



iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)Problema Maestro:



iteracion 2:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0)

Problema Maestro:


z +3w1 +12w2 172

z irr w1 0 w2 0



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}




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)




175 ,1710 , 0)

Subproblema:x3 = (0, 52 , 0, 0)Restriccion violada:

z > wb + (c wA)xj?




175 ,1710 , 0)


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



iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x

3 = (0, 52 , 0, 0)Problema Maestro:



iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x

3 = (0, 52 , 0, 0)

Problema Maestro:


z +3w1 +12w2 172

z 2w1 12w2 52z irr w1 0 w2 0



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}



iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x


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



iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x


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)



iteracion 3:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x


4910 ,

65 , 0)


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



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:



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 +3w1 +12w2 172

z 2w1 12w2 52z + 12w2 112

z irr w1 0 w2 0



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}



iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x

3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)


-5 +min(x51,x5

2)X1{0x51 + 0x52}

x1

x2

+min(x5

3,x5

4)X2{0x53 + 3x54}

x3

x4



iteracion 4:x1 = (0, 0, 0, 0), x2 = (2, 32 , 3, 0),x

3 = (0, 52 , 0, 0), x4 = (2, 32 , 0, 0)


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



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



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)


Relacion entre las Tecnicas de Descomposicion

Problema Maestro de Benders

Max z

s.a z wb + (c wA)xj j = 1, . . . , kz , w irrestrictos



Variables duales

Max z

s.a z wb + (c wA)xj j = 1, . . . , k jz irrestricto



Problema dual

Mink

j=1(wb + (c wA)xj)js.a

kj=1 j = 1

j 0 j = 1, . . . , k



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



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)



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



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



El problema original es:

Min cx

s.a Ax = b

x X


Modelos con muchas restricciones y el problema deseparacion

Problema original

Min cx

s.a Ax bx X

muchas restricciones



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



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



Problema reducido

Min cx

s.a Ax bx X



Nota: cx es una cota inferior para el problema original



Problema reducido

Min cx

s.a Ax bx X



3 Si x satisface todas las restricciones del problema original,entonces es la solucion optima.



Problema reducido

Min cx

s.a Ax bx X




4 Sino, tenemos que agregar restricciones violadas a A, b eiterar.



Problema reducido

Min cx

s.a Ax bx X




4 Sino, tenemos que agregar restricciones violadas a A, b eiterar.

Como encontramos restricciones violadas?65

Tecnicas de Descomposicion R. Medina


Problema reducido

Min cx

s.a Ax bx X

1 Inicializar un problema reducido con un subconjunto de restricciones A, b


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


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



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



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.



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



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



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.



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.



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



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



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}



Conjunto Independiente de Vertices (Stable Set):Iteracion 1:Problema reducido:


x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}

Solucion:





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:





x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}


Max y1 +y3 +y4s.a y3 +y4 1

y1 {0, 1} y3 {0, 1} y4 {0, 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





x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}

Solucion:





x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}






x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}


Max y2 +y3 +y4s.a y2 +y3 1

y3 +y4 1y2 +y4 1

y2 {0, 1} y3 {0, 1} y4 {0, 1}





x1 +x3 1x1 {0, 1} x2 {0, 1} x3 {0, 1} x4 {0, 1} x5 {0, 1} x6 {0, 1}


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


Modelo con muchas variables y la generacion de columnasPrimal

Min cx

s.a Ax bx 0

Dual

Max by

s.a Ay cy 0


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


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


y la solucion dual y



Min cx

s.a Ax bx 0


Max by

s.a Ay cy 0




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.



Min cx

s.a Ax bx 0


Max by

s.a Ay cy 0




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



Min cx

s.a Ax bx 0


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


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



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



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}



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}



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



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.



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:



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}



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




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.



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}




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}




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




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.



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}




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}




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




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.



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



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}


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.


Documents

3_Benders.pdf