PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE Curso: ICS2121-Métodos de Optimización

ESCUELA DE INGENIERÍA Semestre: 01-2019

Departamento de Ingeniería Industrial y de Sistemas Profesor: Gustavo Angulo
Ayudantes: Sebastián Vásquez, José Manuel Comber

Interrogación 3
Duración: 2 horas y 30 minutos.

Considere un grafo dirigido D = (N, A), donde N es el conjunto de nodos y A es el conjunto

de arcos. Existe un conjunto K de commodities que deben ser ruteados a través de la red. Más
precisamente, hay dk > 0 unidades del commodity k que deben ser enviadas desde el origen
sk ∈ N al destino tk ∈ N , siendo vk > 0 su volumen unitario. Además, hasta bka ≥ 0 unidades
del commodity k pueden atravesar el arco a, siendo cka > 0 el costo unitario asociado. Por otro
lado, el volumen total de los commodities que utilizan el arco a no puede exceder la capacidad
ua > 0. Existe la posibilidad de expandir la capacidad de la red, incurriendo en un costo fijo
fa > 0 por arco. En tal caso, el arco a aumenta su capacidad unitaria en b̄ka > 0 para el
commodity k y su capacidad volumétrica total en ūa > 0. Suponga que todos los parámetros
son números enteros y que inicialmente es posible rutear todos los commodities sin necesidad
de expandir la red. Considere la siguiente formulación:
X XX
min fa xa + cka yak (1)
a∈A k∈K a∈A

X X  dk i = sk
s.a yak − yak = −dk i = tk k ∈ K, i ∈ N (2)
0 i 6= sk , tk

a∈δ + (i) a∈δ − (i)

yak ≤ bka + b̄ka xa k ∈ K, a ∈ A (3)

X
vk yak ≤ ua + ūa xa a ∈ A (4)
k∈K
xa ∈ {0, 1} a ∈ A (5)
yak ≥ 0 k ∈ K, a ∈ A. (6)

Pregunta 1 (20 puntos)

Suponga que desea obtener una reformulación de Dantzig-Wolfe para (1)-(6), donde (3) y (4)
se consideran complicantes y x se mantiene en el problema maestro. Sea Pk = {y k ∈ RA :
y k satisface (2), (6)} = conv(Vk )+cone(Rk ), donde Vk = {hkl : l ∈ Lk } y Rk = {wkg : g ∈ Gk }.

1. (3 puntos) De (2) y (6), indique por qué los poliedros Pk pueden ser no acotados.
Solución: Si el grafo tiene algún ciclo dirigido, entonces, a partir de una solución y k
factible, podemos construir otra solución factible aumentando arbitrariamente el flujo a
 través del ciclo, pues este aumento mantiene conservación de flujo (2) y no negatividad
(6). En tal caso, Pk es no acotado.

2. (3 puntos) Indique cómo se representa un elemento cualquiera de Pk en términos de los

elementos de Vk y Rk .
Solución: Por el teorema de Minkowski-Weyl, tenemos y k = l∈Lk λkl hkl + g∈Gk µkg wkg ,
P P

donde l∈Lk λkl = 1, λ ≥ 0, µ ≥ 0.

P

3. (3 puntos) Escriba una reformulación del tipo Dantzig-Wolfe de (1)-(6) a partir de la

representación anterior.
Solución: La reformulación queda
 
X XX X X
min fa xa + cka  λkl hkl
a + µkg wakg 
a∈A k∈K a∈A l∈Lk g∈Gk
X X
s.a λkl hkl
a + µkg wakg ≤ bka + b0ka xa k ∈ K, a ∈ A
l∈Lk g∈Gk
 
X X X
vk  λkl hkl
a + µkg wakg  ≤ ua + u0a xa a∈A
k∈K l∈Lk g∈Gk
X
λkl = 1 k ∈ K
l∈Lk
xa ∈ {0, 1} a ∈ A
λk ≥ 0 k ∈ K
µk ≥ 0 k ∈ K.

4. (5 puntos) Suponga que ha resuelto el problema maestro lineal de su reformulación

definido por un subconjunto de columnas. Dado un vector dual óptimo, indique el costo
reducido de las variables de su reformulación.
Solución: Dados L0k ⊆ Lk y G0k ⊆ Gk para k ∈ K, sea (α, β, σ, ρ) una solución dual
óptima para el problema
  ! ! 
X X X X X X
min fa xa +  cka hkl
a λkl + cka wakg µkg 
a∈A k∈K l∈L0k a∈A g∈G0k a∈A
X X
s.a λkl hkl
a + µkg wakg ≤ bka + b0ka xa k ∈ K, a ∈ A (αak )
l∈L0k g∈G0k
 
X X  X  
 vk hkl k
a λl + vk wakg µkg  ≤ ua + u0a xa a ∈ A (βa )
k∈K l∈L0k g∈G0k
X
λkl = 1 k ∈ K (σk )
l∈L0k

xa ≤ 1 a ∈ A (ρa )
x≥0
λk ≥ 0 k ∈ K
µk ≥ 0 k ∈ K.
El costo reducido de λkl corresponde a
X X X
cka hkl
a − αak hkl
a − βa vk hkl
a − σk .
a∈A a∈A a∈A

El costo reducido de µkg corresponde a

X X X
cka wakg − αak wakg − βa vk wakg .
a∈A a∈A a∈A

5. (3 puntos) Considere el problema de pricing usual sobre Pk . Sabemos que si el valor

óptimo es negativo, entonces agregamos la columna asociada a un vértice óptimo. ¿Qué
debería hacer en este caso si el valor objetivo es no acotado?
Solución: El problema de pricing corresponde a
( )
X X X
min cka hka − αak hka − βa vk hka − σk : hk ∈ Pk .
a∈A a∈A a∈A

Si el valor óptimo es no acotado, entonces existe ŵk ∈ Rk tal que

X X X
cka ŵak − αak ŵak − βa vk ŵak < 0,
a∈A a∈A a∈A

es decir, el costo reducido es negativo. Luego, se debe agregar la columna correspondiente

a dicho vector.
6. (3 puntos) Indique por qué, en este problema, el problema de pricing tiene siempre valor
óptimo finito. Concluya entonces que la reformulación vista en clases es suficiente en este
caso.
Solución: Por dualidad, tenemos αk ≤ 0 y β ≤ 0. Por lo tanto, la función objetivo del
problema de pricing está acotada inferiormente por −σk , por lo que tiene valor óptimo
finito. Por lo tanto, nunca se agregarán columnas asociadas a variables µkg .
Pregunta 2 (20 puntos)

Considere la relajación lagrangiana de (1)-(6) obtenida de penalizar (2) en la función objetivo.

1. (4 puntos) Escriba la función dual asociada a un vector de penalización π y la forma

del dual lagrangiano correspondiente.
Solución: Para k ∈ K e i ∈ N , sea pk ∈ RN definido por pksk = dk , pktk = −dk y pki = 0
para i 6= sk , tk . Así, para π ∈ RK×N , tenemos
 
X XX XX X X
θ(π) = min fa xa + cka yak + πik  yak − yak − pki 
a∈A k∈K a∈A k∈K i∈N a∈δ + (i) a∈δ − (i)

s.a yak
≤ + bka b̄ka xa
k ∈ K, a ∈ A
X
k
vk ya ≤ ua + ūa xa a ∈ A
k∈K
xa ∈ {0, 1} a ∈ A
yak ≥ 0 k ∈ K, a ∈ A.

Finalmente, el dual lagrangiano corresponde a max θ(π) : π ∈ RK×N .



2. (4 puntos) Indique por qué la función dual es separable y escríbala como suma de
funciones adecuadas y definidas de forma precisa.
Solución: La funciónP objetivo es P y las restricciones son separables sobre a ∈ A.
lineal P
Por lo tanto θ(π) = a∈A θa (π) − k∈K i∈N πik pki , donde para a = (i, j) ∈ A definimos
X X 
θa (π) = min fa xa + cka yak + πik − πjk yak
k∈K k∈K
s.a yak
≤ + bka b̄ka xa
k∈K
X
vk yak ≤ ua + ūa xa
k∈K
xa ∈ {0, 1}
yak ≥ 0 k ∈ K.

3. (4 puntos) Muestre que cada una de las funciones previamente definidas se puede evaluar
resolviendo dos problemas de programación lineal.
Solución: Claramente, tenemos θa (π) = min θa0 (π), θa1 (π) , donde para q = 0, 1 defini-


mos
X X 
θaq (π) = min fa q + cka yak + πik − πjk yak
k∈K k∈K
s.a yak k k
≤ b + b̄a q k ∈ K
X a
vk yak ≤ ua + ūa q
k∈K
yak ≥ 0 k ∈ K.
 4. (4 puntos) ¿Cómo se compara la cota obtenida del dual lagrangiano con la cota de la
relajación lineal de (1)-(6)?
Solución: El poliedro asociado a la relajación lineal correspondiente a θa (π) es, en general,
no integral. Luego, el dual lagrangiano entrega una cota que es mayor o igual a la de la
relajación lineal de (1)-(6), pudiendo ser estrictamente mayor.

5. (4 puntos) Indique cómo obtener un supergradiente de la función dual.

Solución: Para π ∈ RK×N , sea (x̂, ŷ) una solución óptima del problema asociado a θ(π).
Tenemos entonces que z ∈ RK×N definido por zik = a∈δ+ (i) ŷak − a∈δ− (i) ŷak − pki es un
P P
supergradiente de la función dual en π.

Pregunta 3 (20 puntos)

Considere la relajación lineal de (1)-(6), la cual desea resolver mediante descomposición de

Benders utilizando y como variables de primera etapa.

1. (5 puntos) Indique la forma de la descomposición, donde el problema maestro queda en

función del valor óptimo de un subproblema adecuado.
Solución: La descomposición queda de la forma
XX
min cka yak + η
k∈K a∈A
s.a Q(y) ≤ η

X X  dk i = sk
yak − yak = −dk i = tk k ∈ K, i ∈ N
0 i 6= sk , tk

a∈δ + (i) a∈δ − (i)

yak ≥ 0 k ∈ K, a ∈ A,

donde
X
Q(y) = min fa xa
a∈A
yak ≤ bka + b̄ka xa k ∈ K, a ∈ A
X
vk yak ≤ ua + ūa xa a∈A
k∈K
xa ≤ 1 a ∈ A
x ≥ 0.

2. (5 puntos) Indique por qué el subproblema es separable y escríbalo como suma de

funciones adecuadas y definidas de forma precisa.
Solución: La función objetivo es lineal y las restricciones son separables sobre a ∈ A.
 P
Por lo tanto Q(y) = a∈A Qa (y), donde para a ∈ A definimos

Qa (y) = min fa xa
yak ≤ bka + b̄ka xa k ∈ K (γak )
X
vk yak ≤ ua + ūa xa (νa )
k∈K
xa ≤ 1 (φa )
xa ≥ 0.

3. (5 puntos) Formule los problemas duales asociados a las funciones previamente definidas.
Solución: Por dualidad, tenemos
!
X  X
Qa (y) = max yak − bka γak + vk yak − ua νa − φa
k∈K k∈K
X
s.a b̄ka γak + ūa νa − φa ≤ fa
k∈K
γak ≥ 0 k∈K
νa ≥ 0
φa ≥ 0.

4. (5 puntos) Determine la forma de las restricciones que deben ser agregadas al problema
maestro.
Solución: Las restricciones tienen la forma
!
X  X
yak − bka γ̂ak + vk yak − ua ν̂a − φ̂a ≤ η,
k∈K k∈K

donde para cada a ∈ A, (γ̂a , ν̂a , φ̂a ) es un vértice dual.