Pr´ actica No8 Desigualdades V´ alidas - Algoritmos de Planos de Corte - Algoritmos Branch & Cut 8.1 Para cada uno de los siguientes conjuntos, encontrar una desigualdad v´alida que agregada a la formulaci´ on sirva para obtener la c´apsula convexa. Verificar graficamente. a) X = {x ∈ B 2 /3x1 − 4x2 ≤ 1} b) X = {(x, y) ∈ R+ × B 1 /x ≤ 20y, x ≤ 7} c) X = {(x, y) ∈ R+ × Z 1 /x ≤ 6y, x ≤ 16} 8.2 Sea P = {x : Ax ≤ b, x ≥ 0}. Mostrar que αx ≤ β es v´alida si y s´olo si existe u ≥ 0 tal que uA ≥ α y ub ≤ β. 8.3 Supongamos que un PPL tiene las siguientes restricciones:

2x1 +3x2 +4x3 ≤24 x1 +2x2 − x3 ≤15 x1 ,

x2 , x 3 ≥ 0

Deducir cotas superiores para x1 , x2 , x3 . P P 8.4 Sea S = {x/ j∈N1 aj xj − j∈N2 aj xj ≤ b, xj ∈ {0, 1}} con aj > 0 para todo j. Dar condiciones necesarias y suficientes para: a) S vac´ıo. b) Todo vector 0,1 pertenece a S. c) xj = 0, j ∈ N1 , para todo x en S. d ) xj = 1, j ∈ N2 , para todo x en S. e) xi + xj ≤ 1, i, j ∈ N1 , para todo x en S. 2 8.5 Sea P = {x ∈ Z+ /−x1 +x2 ≤ 1/2, 1/2x1 +x2 ≤ 5/4, x1 ≤ 2}. Mostrar que −1/4x1 −x2 ≤ 1/2 es una desigualdad v´ alida. 4 /4y1 + 5y2 + 9y3 + 12y4 ≤ 34}. 8.6 Probar que y2 + y3 + 2y4 ≤ 6 es v´ alida para X = {y ∈ Z+

8.7 En cada uno de los siguientes ejemplos, encontrar una desigualdad v´alida para X que corte al punto x dado: 2 a) X = {(x, y) ∈ R+ × B 1 /x1 + x2 ≤ 2y, xj ≤ 1 j = 1, 2} (x1 , x2 , y) = (1, 0, 0,5) 2 b) X = {(x, y) ∈ R+ × Z 1 /x1 + x2 ≤ 25, x1 + x2 ≤ 8y} (x1 , x2 , y) = (20, 5, 25/8) 5 c) X = {x ∈ Z+ /9x1 + 12x2 + 8x3 + 17x4 + 13x5 ≥ 50} (x1 , x2 , x3 , x4 , x5 ) = (0, 25/6, 0, 0, 0)

8.8 Derivar desigualdades v´ alidas para P = {x ∈ B6 : 40x1 + 40x2 + 35x3 + 35x4 + 15x5 + 15x6 ≤ 100, xj ∈ {0, 1}j = 1, . . . , 6} Son cortes para x = (1, 1/2, 0, 1/2, 1/2, 1), x = (1/3, 1, 1/3, 1/3, 1/3, 1)? 1

8.9 Considerar el problema

Min

x1 +

x2

s.a.

x1 +

x2 ≥4

0,5x1 +2,5x2 ≥2,5 2 x ∈Z+

Mostrar que x∗ = (15/4, 1/4) es la soluci´on ´optima de la relajaci´on lineal y encontrar una desigualdad v´ alida que corte a x∗ . 8.10 Consideremos el siguiente problema

Min s.a.

3

x1 + x2 +

x3 + x4 + x5

x1 +2x2 +

x3 +2x4 + x5 ≥4

− 2x1 +6x2 +5 x3 −2x4 −4x5 ≥2 4

x1 −4x2 −14x3 +2x4 +3x5 ≥4 x1 ,

x2 ,

x3 ,

x4 , x5

binarias

a) Resolver usando enumeraci´ on impl´ıcita. b) Verificar que 5x1 + 4x2 − 8x3 + 2x4 ≥ 10 es desigualdad v´alida. c) Agregar la desigualdad anterior y resolver por enumeraci´on impl´ıcita. 8.11 Resolver usando cortes de Gomory: a) Max

7x1 +6x2 x1 +3x2 ≤6

s.a.

2x1 + x2 ≤9 x1 ,

x2 ≥0 enteras

b) Max s.a.

2x1 +4x2 + x3 3x1 + x2 +2x3 ≤12 x1 +2x2 − x3 ≤ 6 x2 , x3 ≥ 0 enteras

x1 ,

n n 8.12 Sea P = {x : ax ≤ b, xj ∈ {0, 1}j = 1, . . . , n} con aj ∈ Z+ , b ∈ Z+ , aj ≤ b, N = {1, 2, . . . , n}. R Sea x el vector caracter´ıstico de R ⊆ N , es decir xj = 1 si j ∈ R, xj = 0 si j ∈ / R. Sea C ⊆ N . Si xC pertenece a P diremos que C es conjunto independiente, en caso contrario, C es conjunto dependiente. P Demostrar que si C es conjunto dependiente entonces j∈C xj ≤ |C| − 1 es desigualdad v´ alida.

8.13 Considerar una instancia del problema generalizado de transporte Min s.a.

P P c x Pi j ij ij x ≤ Pj ij a x ≥ i ij i mn x ∈ Z+

bi dj

2

para i = 1, . . . , m para j = 1, . . . , n

con m = 4, n = 6, a = (15, 25, 40, 70), b = (10, 5, 7, 4), d = (45, 120, 165, 214, 64, 93) y

 23 29 c= 43 54

12 24 31 36

34 43 52 54

25 35 36 46

27 28 30 34

 16 19  21 27

a) Resolver usando un paquete de programaci´on entera mixta. b) Resolver la relajaci´ on lineal. Analizando la soluci´on agregar una o m´as desigualdades v´ alidas a la formulaci´ on y volver a resolver el problema. Comparar la cantidad de nodos del branch and bound en ambos casos. Tratar de minimizar el n´ umero de nodos. 8.14 Considerar el siguiente problema de telecomunicaciones. Para cada par de nodos se conoce la demanda. El problema consiste en instalar suficiente capacidad en los ejes del grafo de modo que todas las demandas puedan ser satisfechas simultaneamente. Si existe una flujo de comunicaciones que tiene que ir de i a j y otro de j a i, la capacidad disponible de la red debe ser mayor o igual a la suma de los dos flujos. La capacidad puede ser instalada en unidades de 1 o 24, que cuestan 1 y 10 respectivamente. Para un grafo de 6 nodos, la demanda es la siguiente: d12 d23 d35 d14

= 12 d13 = 51 = 53 d24 = 51 = 32 d45 = 91 = d15 = d25 = d34 = 0

Formular y resolver con un paquete de programaci´on entera mixta el problema de instalar la capacidad suficiente en la red a costo m´ınimo. Tratar de ajustar la formulaci´on. 8.15

a) Sea X = {x ∈ B 5 /3x1 − 4x2 + 2x3 − 3x4 + x5 ≤ −2}. Mostrar como pueden derivarse las desigualdades v´ alidas x2 + x4 ≥ 1 y x1 ≤ x2 como desigualdades C-G. b) Considerar el conjunto X = {x ∈ B 4 /xi + xj ≤ 1 para todo i, j}. Mostrar como las desigualdades v´ alidas x1 + x2 + x3 ≤ 1 y x1 + x2 + x3 + x4 ≤ 1 pueden derivarse como desigualdades C-G.

2 /x1 −x2 ≥ −11, x1 −x2 ≤ 3, 2x1 +6x2 ≤ 15, 2x1 +4x2 ≤ 8.16 Considerar el conjunto X = {x ∈ Z+ 7}. Encontrar todas las soluciones factibles y encontrar gr´aficamente la descripci´on minimal de la c´ apsula convexa de X. P 8.17 Sea X = {x ∈ B nP / j∈N aj xj ≤ b} con aj > 0 para j ∈ N y b > 0. Mostrar que la desigualdad v´ alida j∈N P πj xj ≤ π0 con π0 > 0 y πj < 0 para j ∈ T 6= ∅ est´a dominada por la desigualdad v´ alida j∈N m´ ax{πj , 0} xj ≤ π0 .

8.18 Mostrar que si πx ≤ π0 + α(xj − k) y πx ≤ π0 + β(k + 1 − xj ) con α, β > 0, k fijo son v´alidas para un poliedro P ⊆ Rn entonces πx ≤ π0 es v´alida para P ∩ {x/xj ∈ Z}. Una desigualdad generada de esta forma se llama una D-desigualdad. 8.19 En cada uno de los siguientes ejemplos, encontrar una desigualdad v´alida para X que corte al punto x∗ dado: 8.20

a) X = {x ∈ B 5 /9x1 + 8x2 + 6x3 + 6x4 + 5x5 ≤ 14} x∗ = (0, 5/8, 3/4, 3/4, 0) b) X = {x ∈ B 5 /12x1 − 9x2 + 8x3 + 6x4 − 3x5 ≤ 2} x∗ = (0, 0, 1/2, 1/6, 1)

3

8.21 Considerar el siguiente conjunto de soluciones de una restricci´on de mochila X = {x ∈ B 6 /12x1 + 9x2 + 7x3 + 5x4 + 5x5 + 6x6 ≤ 14} Poner x1 = x2 = x4 = 0 y considerar la desigualdad cover x3 + x5 + x6 ≤ 2. Encontrar a partir de esta, una desigualdad v´alida para X ”mejor”, de la forma α1 x1 + α2 x2 + α3 x4 + x3 + x5 + x6 ≤ 2. 8.22 Dado un grafo G = (V, E) con n = |V | considerar el conjunto de vectores soluciones de X del n problema de conjunto independiente X P= {x ∈ B /xi + xj ≤ 1 para toda arista e = (i, j)}. Mostrar que la desigualdad de clique j∈C xj ≤ 1 para C clique maximal de G, es v´alida. 8.23 Considerar la siguiente instancia del problema de asignaci´on generalizado max sujeto a

P

P

i∈M

j∈N

cij xij

P x Pj∈N ij i∈M aij xij

= ≤

para todo i ∈ M para todo j ∈ N

1 bj

con m = 10, n = 5, b = (80, 63, 75, 98, 59), aij y cij dados por las siguientes tablas: aij 1 2 3 4 5 6 7 8 9 10

1 3 15 54 92 19 91 15 47 34 35

2 24 23 43 83 10 55 25 43 23 23

3 53 43 27 45 33 32 35 35 52 34

4 27 74 21 35 43 26 37 32 46 25

5 17 23 36 23 12 23 28 37 43 40

cij 1 2 3 4 5 6 7 8 9 10

1 15 19 10 60 21 67 23 23 15 10

2 44 23 6 45 12 65 34 25 13 15

3 76 45 3 34 34 34 44 32 23 23

4 43 46 23 36 44 20 47 15 24 12

5 34 34 15 23 10 37 32 27 34 12

Resolver el problema con un paquete de programaci´on entera. Agregar desigualdades v´alidas para reducir el n´ umero de nodos. 8.24 Hay que asignar frecuencias a 10 estaciones de radio, dentro del rango {1, . . . , 6} para cada par de estaciones hay un par´ ametro de interferencia que es la m´ınima diferencia que tienen que tener las frecuencias: dif12 = 1 dif67 = 1 dif210 = 1

dif23 = 2 dif78 = 1 dif310 = 1

dif34 = 4 dif89 = 2 dif510 = 4

dif45 = 2 dif910 = 3 dif710 = 2

dif56 = 3 dif18 = 2 dif25 = 2

el resto es 0. Resolver el problema de minimizar el rango de las frecuencias asignadas.

4

8.25 Dos ciclistas tienen que repartir el diario a 60 clientes de un barrio, recogi´endolos desde el punto de distribuci´ on a las 6 de la ma˜ nana. Se supone que las manzanas del barrio son regulares y que podemos asumir que las distancias entre dos puntos (x1 , x2 ) y (y1 , y2 ) es |x1 − y1 | + |x2 − y2 |. Las coordinadas de los clientes son: 17,310 59,250 85, 419 110,447 122,104 161,190 167,399 182,359 186,440 211,27 233,27 286,24

39,85 59,476 89,418 118,413 133,410 161,414 178,409 184,76 188,63 212,140 235,405 292,148

48,403 62,353 105,476 120,49 142,439 161,434 179,265 184,198 194,433 222,181 239,229 299,188

49,444 81,441 109,258 120,451 145,412 162,458 179,365 185,124 197,352 223,21 276,231 302,184

55,153 85,367 110,441 120,459 146,364 165,374 179,427 186,169 200,376 223,328 284,362 317,237

El dep´ osito est´ a en (375, 375). Asumiendo que los ciclistas cubren una distancies de 300 por hora, cu´ al es la hora m´ as temprana en que pueden terminar la distribuci´on de todo los diarios?

5