Programacion entera

Programaci´n Entera o
Marcel Goic F.1
Pag. 1

1.

Algoritmo de planos cortantes fraccionales de Gommory

Consideremos el problema (P ) m´x{cT x|Ax = b, x ∈ Z+ }. Resolveremos la relajaci´n lineal a o de (P ) y a partir de dichas soluciones generaremos una desigualdad v´lida que separe la a soluci´n del conjunto factible. Al resolver una relajaci´n cualquiera llegamos a la siguiente o oforma estandar: m´x a00 + a ¯
j∈N B

a0j xj ¯ u = 1...m

s.a xu + B

j∈N B

auj xj ≤ au0 ¯ ¯ x ≥ 0

Si xB ∈ Z, entonces la soluci´n es ´ptima para el problema original. o o Si ∃u tal que xu ∈ Z, entonces separamos xB del poliedro Ax = b a traves del siguiente B / corte de Gommory: (¯uj − auj )xj ≥ au0 − au0 a ¯ ¯ ¯
j∈N B

Gommory Cut

Proposici´n o
Sean: ´ B −1 : inversa de la baseoptima de un problema lineal entero relajado. −1 β : fila u de B . qi : βi − βi Entonces, el corte de Gommory puede escribirse como:
n j=1

q T aj x j ≥ q T b

Gommory Cut

2.

Desigualdades v´lidas fuertes a

En general, encontrar una desigualdad v´lida no es suficiente para fortalecer el problema. a Queremos encontrar aquellas desigualdades que generen la envoltura convexa del poliedroen las vecindades del ´ptimo. Para ello no existe un procedimiento general por lo que debe o estudiarse para cada tipo de problema. En este curso, s´lo veremos el caso de los problemas o tipo 0-1 knapsack.

IN70K: Programaci´n Matem´tica o a

Pag. 2

2.1.

Procedure to lift cover inequalities.

Sea X = {x ∈ {0, 1}n | n aj xj ≤ b}. Sea C una cobertura m´ ınima de X y N \C = j=1 ındicesque no pertenecen a la cobertura. {j1 , j2 , ..., jr } el conjunto de ´ ´ t=1: inicializacion Tenemos la desigualdad
j∈C

xj ≤ |C| − 1.

´ ´ t=t: iteracion generica
t−1 Tenemos la desigualdad j∈C xj ≤ |C| − 1. Para encontrar αjt que i=1 αji xji + t−1 agregar a la restricci´n αjt xjt + i=1 αji xji + j∈C xj ≤ |C| − 1 debemos resolver un o knapsack-problem auxiliar: t−1

a ζt = m´x
i=1

αjixji +
j∈C

xj

s.a

t−1 i=1

aji x ji +

j∈C

a j x j ≤ b − aj t x ∈ {0, 1}|C|+t−1

Entonces, αjt = |C| − 1 − ζt • Si t = r, parar. • Si t < r, t := t + 1, seguir.

3.
3.1.

Problemas
Problema 1.

Resuelva el siguiente problema de programaci´n entera: o (P ) m´x z = 3x2 + 4x4 a s.a 4x1 + x2 − 4x3 + x4 ≤ 2 (1) (2) 2x1 − 5x3 ≥ −3 x1 , x2 , x3 , x4 ∈ {0, 1} Hint: Le puede serde utilidad preprocesar el problema para evitar tener que incurrir en un esquema de branch & bound.

IN70K: Programaci´n Matem´tica o a 3.1.1. Soluci´n o

Pag. 3

En general, para enfrentar este problema debieramos recurrir a un esquema de branch & bound. Sin embargo, para simplifiar el problema procederemos previamente a realizar un preprocesamiento: (1) ⇒ x1 ≤ x3 . En efecto, para que x1pueda tomar el valor 1 necesariamente la variable x3 debe tomar el valor 1. (2) ⇒ x1 ≥ x3 . En efecto, para que x3 pueda tomar el valor 1 necesariamente la variable x1 debe tomar el valor 1. De lo anterior, se concluye que x1 = x3 . Luego el problema puede expresarse como: (P ) m´x z = 3x2 + 4x4 a s.a x2 + x4 ≤ 2 (1) (2) x1 ≤ 1 x1 , x2 , x4 ∈ {0, 1}

Como x1 ∈ {0, 1}, es claro que la segundarestricci´n es redundante. Luego el problema queda o con una unica restricci´n en la que es f´cil encontrar la soluci´n por inspecci´n: (0,0,0,2)2 . ´ o a o o

3.2.

Problema 2.

Considere el siguiente problema de programaci´n entera: o (P ) m´x z = x1 + x2 a s.a −x1 + 3x2 ≤ 6 3x1 − x2 ≤ 3 x1 , x2 ∈ Z+ 1. Plantee y resuelva la relajaci´n lineal del problema (P ), escribiendo expl´ o ıcitamenteel valor de las variables b´sicas, no b´sicas y la matriz b´sica inversa. ¿Es ´ptima la a a a o soluci´n relajada? ¿Cu´l es el ´ptimo del problema (P)?. o a o 2. Encuentre un corte de Gomory que separe la soluci´n del problema relajado del espacio o de soluciones factibles. Grafique dicho corte en el plano x1 x2 .
en estricto rigor el problema es muy degenerado ya que cualquier tupla de la forma...