ICS 2121 Métodos de Optimización, Sem 2020-1

Prof. Jorge Vera

Interrogación 2, parte 2, Solución

Pregunta 1 (12 puntos):

a) (6 puntos): Considere el siguiente problema de optimización:

min f (x)
kxk1 ≤β

donde
f (x) = max{γ, kxk22 } + kAx − bk22 }

y tanto γ > 0 como β > 0 son valores dados.

Indique qué algoritmo de los revisados hasta ahora en el curso podrı́a usar para abordar este problema. Su respuesta
debe ser bien justificada, argumentando sobre las propiedades del problema y de cómo se adaptan al algoritmo que
usted propone. Haga también una estimación de la eficiencia que tendrá su algoritmo, justificando adecuadamente. No
tiene que mostrar el desarrollo del algoritmo, sólo responda lo que se le pregunta pero en forma justificada y haciendo
referencia a los contenidos del curso.

Solución: Se puede notar que f es convexa, pero no diferenciable. Además, el conjunto D = {x ∈ Rn : ||x||1 ≤ β} es
convexo y ”simple” en el sentido discutido en clases. Por lo tanto, un algoritmo para abordar este problema es usar
el método proyectado en conjunto con el método del subgradiente, es decir, usar la etapa xk+1 = ΠD (xk + λk dk ) con
−dk ∈ ∂f (xk ). Las convergencias son iguales al caso sin restricciones y se usan los mismos λ para los pasos, por lo que
la complejidad de este método es O( 12 ) (o O( √1 ) si se considera en conjunto con el método acelerado).

Detalle del puntaje:

• 2 puntos por indicar los supuestos que permiten usar el algoritmo.

• 2 puntos por indicar el algoritmo.

• 2 puntos por indicar la eficiencia del algoritmo.

b) (6 puntos): Considere el siguiente problema de programación lineal entera binaria:

min cT x
s.a. aTi x ≥ bi , i = 1, . . . , m
xj ∈ {0, 1}, j = 1, . . . , n

donde ai ∈ Rn , i = 1, . . . , m, c ∈ Rn y los bi son escalares. Muestre de qué manera este problema podrı́a ser resuelto
mediante Programación Dinámica. Para esto muestre una formulación usando una ecuación recursiva (o sea, una
Ecuación de Bellman) con una función de valor adecuada y explicitando una función de transición.
 Solución: La formulación en su enfoque DP viene dada por la siguiente ecuación de Bellman,
n
X
Gt (d) = min cj xj
j=t
n
X
s.t. aij xj ≥ di i = 1, . . . , m (1)
j=t

xj ∈ {0, 1} j = t, . . . , n (2)

que en su forma recursiva queda,

Gt (d) = min {ct xt + Gt+1 (Ft (d))} Ft (d) = {di − ait xt }i , i = 1, . . . , m

xt ∈{0,1}

donde se tiene que,

Gn (d) = min cn xn
s.t. ain xn ≥ di i = 1, . . . , m (1)
xn ∈ {0, 1} (2)
mientras lo que queremos determinar viene dado por:

z ∗ = G1 (b)

Detalle del puntaje:

• 1 puntos por la ec. de Bellman en su forma extendida

• 2 puntos por la ec. de Bellman en su forma recursiva

• 1 punto por la función de transición

• 1 punto por la inicialización de la recursión en t = n

• 1 punto por evidenciar lo que se está buscando (parada)

c) (3 puntos de bono): Considere el siguiente problema de optimización lineal:

min cT x
P)
s.a. aTi x ≤ bi , i = 1, . . . , m

donde ai ∈ Rn , i = 1, . . . , m, c ∈ Rn y los bi son escalares.

Un problema importante para la eficiencia de los algoritmos (por ejemplo el Simplex) es “limpiar” el problema ini-
cialmente en una etapa de preprocesamiento en donde se eliminan restricciones redundantes. Para ser especı́ficos,
vamos a decir que la restricción k, donde k ∈ {1, . . . , m} es redundante en el problema P ) si cualquier x que cumpla
aTi x ≤ bi , i 6= k cumple con aTk x ≤ bk . Es decir, la restricción k está “de más”, basta con las otras m − 1 restricciones.
Usando el Lema de Farkas, determine una condición que deba cumplirse entre los datos de las restricciones y que
permita determinar si acaso la restricción k es redundante en el problema P ).
Solución: A partir de la definición se tiene que la restricción k es redundante si el siguiente sistema es infactible:

aTi x ≤ bi i 6= k
aTk x > bk

Reordenando y haciendo más explı́cito el sistema de ecuaciones resulta:

a11 x1 + ... + a1n xn ≤ b1

..
.
−ak1 x1 − ... − akn xn < −bk
..
.
am1 x1 + ... + amn xn ≤ bm

A partir del Lema de Farkas, si el sistema anterior es infactible, entonces existen µi ≥ 0, i 6= k y t ≥ 0 tal que:
P
aij µi − akj t = 0 j = 1, ..., n
i6=k
P
bi µi − bk t < 0
i6=k

Es posible notar que si t = 0, entonces el sistema de las m − 1 restricciones (distintas a la k) es infactible (por el
mismo Lema), pero entonces no tiene sentido hablar de redundancia de la k-ésima restricción, por lo tanto se debe
tener que t > 0. Llamemos ci = µi /t, i 6= k. A partir de lo desarrollado, se puede concluir que la restricción k es
P P
redundante si existen ci ≥ 0, i 6= k tal que bk > bi ci y akj = aij ci para j = 1, ..., n (esto último significa que,
i6=k i6=k
para j = 1, ..., n, los akj se pueden expresar como combinación lineal de los aij usando los ci ≥ 0 como pesos, con i 6= k).

Detalle del puntaje:

• 2 puntos por plantear el sistema que debe ser infactible y usar el Lema de Farkas.

• 1 punto por conclusión.

Pregunta 2 (12 puntos)
Una empresa necesita definir la cantidad de empleados que debe asignar en distintos turnos de trabajo para un periodo de 24
horas. Los turnos están diseñados para que sea posible atender ciertas ventanas de tiempo en las que se requieren cantidades
mı́nimas de personal. La siguiente tabla muestra seis posibles turnos y 12 ventanas de tiempo:

Por supuesto, puede haber muchos más esquemas de turnos que los seis mostrados aquı́. Los turnos que se definan deben
cumplir con el siguiente conjunto de condiciones:

1. Cada turno consiste en trabajar entre 2 y 4 ventanas de tiempo no necesariamente consecutivas.

2. Los turnos que cubran las ventanas de la noche y madrugada, de 00 a 6 horas, deben ser de exactamente 2 ventanas
entre esas horas, no necesariamente consecutivas (por ejemplo, en la tabla el turno 5 cubre dos ventanas y el turno 6
cubre otras dos, más una fuera de esas horas).

3. Si un turno tiene asignadas ventanas de la noche y madrugada, de 00 a 6 horas, entonces sólo puede haber a lo más
una ventana asignada en los otros horarios (eso pasa, por ejemplo, con el turno 6 en la tabla).

Diremos que un turno es “válido” si cumple con las condiciones anteriores. Sea n el número total de turnos válidos y sea T
el número de ventanas de tiempo (12 en este caso). Sea dt , la cantidad mı́nima de empleados requerida para la ventana de
tiempo t, t = 1, . . . , T . El salario por trabajar en la ventana t es st y el salario total para un empleado que trabaja en un
turno j, y que denotamos wj , es la suma de los salarios st para las ventanas que forman el turno. Usaremos un parámetro
ajt el cual tomará el valor 1 si el turno j cubre la ventana de tiempo t y 0 si no.

La empresa desea determinar cuántos empleados asignar a cada turno de modo de cumplir con las necesidades mı́nimas de
personal en cada bloque de tiempo, y hacerlo a mı́nimo costo. Definamos una variable xj , entera, que corresponde a la
cantidad de personas a contratar para el turno j. El modelo que resuelve el problema es:
n
P
min w j xj
j=1
Pn
s.a. ajt xj ≥ dt , t = 1, . . . , T.
j=1

xj ≥ 0 entero , j = 1, . . . , n.

a) (4 pts) En primer lugar, argumente que las reglas descritas que deben cumplir los turnos, permiten efectivamente generar
suficientes turnos para cubrir todas las ventanas. Escriba explı́citamente en forma matemática las condiciones que deben
cumplir los parámetros ajt , para que el turno j sea válido.
 Solución: En el ejemplo de la tabla es posible apreciar que hay suficientes patrones para cubrir los requerimien-
tos necesarios. Sea J el conjunto de todos los turnos j válidos, las condiciones que deben cumplir estos, usando los
parámetros ajt , son:

1. Cada turno consiste en trabajar entre 2 y 4 ventanas de tiempo no necesariamente consecutivas

12
X
2≤ ajt ≤ 4 ∀j ∈ J
t=1

2. Los turnos que cubran las ventanas de la noche y madrugada, de 00 a 6 horas, deben ser de exactamente 2 ventanas
entre esas horas, no necesariamente consecutivas. Para ello se debe cumplir que si:
12
X 9
X
ajt = 2 → ajt ≤ 1
t=10 t=1

Por otro lado, si un turno tiene asignadas ventanas de la noche y madrugada, de 00 a 6 horas, entonces sólo puede
haber a lo más una ventana asignada en los otros horarios.

Para representar las dos condiciones anteriores, se utiliza una variable auxiliar binaria z:
12
X
ajt = 2z
t=10

9
X
ajt ≤ z + 4(1 − z)
t=1

Detalle del puntaje: 1 punto por explicación, 1 punto por cada formulación matemática de las condiciones sobre ajt .

b) (8 pts) Ahora explique cómo resolver la relajación lineal del problema (es decir, sin incluir la restricción de enteros, sólo
xj ≥ 0) usando Generación de Columnas. En particular, describa con precisión el problema Maestro y el Satélite que
se deben usar y cómo se van “generando” las columnas.(Se calificarán 3 puntos por el maestro, 3 por el satélite y 2 por
los otros detalles del algoritmo).

Solución: Para aplicar el algoritmo de generación de columnas, debemos:

• Partiremos la resolución del algoritmo de generación de columnas con un conjunto inicial de columnas que podemos
llamar J, y digamos que tiene una j cantidad inicial de turnos, ya generados y conocidos.

• Ahora, debemos resolver el problema maestro comenzando con un número reducido de columnas:

J
X
min wj xj
j=1
J
X
s.a. ajt xj ≥ dt ∀t = {1, ..., T }
j=1

xj ≥ 0 ∀j = {1, ..., J}
 • Sean π los multiplicadores duales del Simplex de una iteración. Queremos utilizarlos para realizar el problema de
”pricing”, es decir, buscar una columna con costo reducido negativo, para que dicha columna pueda ingresar a
nuestra base. Dicho costo está dado por:

12
X 12
X 12
X
ŵj = wj − π T Aj = ajt st − ajt πt = ajt (st − πt )
t=1 t=1 t=1

Entonces, el problema satélite consiste en minimizar este valor:

12
X
ρ = min ut (st − πt )
t=1
12
X
s.a. ut ≥ 2
t=1
12
X
ut ≤ 4
t=1
12
X
ut = 2z
t=10
9
X
ut ≤ z + 4(1 − z)
t=1

ut ∈ {0, 1} ∀t = {1, ..., 12}

z ∈ {0, 1}

La variable ut = {1 si se usa la ventana t, 0 en otro caso }, por lo tanto, sus valores corresponden a los coeficientes
ajt que definen un patrón de turno. Además se utiliza una variable auxiliar z para representar la segunda condición.
P12
• Si ρ < 0, la solución del satélite entrega una columna para agregar al problema maestro con costo t=1 ut st . En
este caso, se actualiza el conjunto J. En caso contrario, se termina el algoritmo.

Detalle del puntaje: 3 puntos por problema maestro correcto, 3 puntos por problema satélite correcto y 2 puntos por
explicar cómo se generan las columnas
Pregunta 3 (16 puntos):
Uno de los problemas principales que enfrenta cualquier gran hospital complejo es la programación de las operaciones en
los quirófanos. Suponga que quiere ayudar a un hospital a la programación de las operaciones durante un perı́odo dado
(una semana, por ejemplo), para lo cual debe determinar qué quirófanos serán usados y qué operaciones se realizarán en qué
quirófano. No nos preocuparemos del orden de las operaciones en dı́as particulares ya que esa decisión se toma en un horizonte
de tiempo más corto. Tenemos N quirófanos y cada quirófano está disponible T horas, en tiempo normal, en el perı́odo. Se
deben organizar un total de P operaciones y la duración de la operación i es de wi horas. De ser eventualmente necesario, un
quirófano puede funcionar tiempo extra, pero el total de tiempo extra entre todos los quirófanos no puede superar Q horas.
Existe un costo fijo Kj por usar el quirófano j en el perı́odo y un costo adicional cj por hora de sobretiempo que se asigne al
quirófano j. Se debe hacer una asignación de operaciones a quirófanos tratando de asignar todas las operaciones, pero si una
operación no es programada (por falta de capacidad), el hospital incurrirá en un costo adicional igual a βi para la operación
i debido a que el paciente debe ser trasladado a otro centro de salud. El siguiente modelo de optimización determina qué
quirófanos usar, qué operaciones asignar a cada quirófono, y cuánto sobretiempo asignar de modo de minimizar los costos
totales. La variables yj indica si un quirófano se usa o no, la variables xij indica si la operación i se hace en el quirófano j,
la variable binaria zj indica si una operación no fue asignada y tj es la cantidad de sobretiempo asignado al quirófano j:
N
P P
P
min {Kj yj + cj tj } + βi zi
j=1 i=1
PN
s.a. xij + zi = 1, i = 1, . . . , P (1)
j=1
PP
wi xij ≤ T yj + tj , j = 1, . . . , N (2)
i=1
N
P
tj ≤ Q, (3)
j=1

xij , yj , zi ∈ {0, 1}, tj ≥ 0, i = 1, . . . , P ; j = 1, . . . , N. (4)

a) (7 pts) Este problema puede ser visto como uno con restricciones complicantes. Identifique un conjunto de restricciones
complicantes y plantee una relajación lagrangeana para esto, es decir, debe explicitar el problema dual e indicar qué
tipo de problema resulta en la función dual. También indique, basado en los contenidos del curso, cómo cree usted
que será la calidad de la cota que obtendrı́a a través de esta relajación. No tiene que dar detalles del algoritmo para
resolver el dual, sólo plantee los problemas con claridad y responda lo que se le pregunta.

Solución: Para determinar qué restricción relajar, se puede proponer (3), ya que al relajarla el problema resultante es
de programación entera, lo cual no es fácil de resolver. Se debe poner especial atención en que si el problema resultante
es muy fácil de resolver, la cota obtenida será mala.
En este sentido, una segunda alternativa es relajar (1). Al hacerlo, el problema resultante es medianamente complejo,
por lo que la cota serı́a decente. Si se relaja (2), la variable tj queda en una sola restricción, por lo que el problema
puede ser separable. Luego, si se relaja (1) y (3), la relajación no es trivial ya que la restricción (2) vincula todas las
variables y la cota no serı́a tan mala. Finalmente, si se relaja (1) y (2) u otra combinación, la cota es mala y se pierde
el sentido de utilizar relajación lagrangeana para definir cotas. Si se relaja la restricción (3), el lagrangeano es de la
forma:
N
P P
P N
P
L(x, λ) = {Kj yj + cj tj } + βi zi + λ{ tj − Q}
j=1 i=1 j=1

Luego, con este lagrangeano dual, se define la función dual:

θ(λ) = min L(x, λ)

N
P
s.a. xij + zi = 1, i = 1, . . . , P (1)
j=1
PP
wi xij ≤ T yj + tj , j = 1, . . . , N (2)
i=1
xij , yj , zi ∈ {0, 1}, tj ≥ 0, i = 1, . . . , P ; j = 1, . . . , N. (4)

Se resuelve entonces el problema:

w∗ = max θ(λ)
s.a. λ≥0
Este problema resultante dual consiste en maximizar una función cóncava que es más simple de resolver que el problema
original.
La calidad de la cota depende de la(s) restricción(es) que se relaje(n). En este sentido, la mejor cota será relajar (3) ya
que el problema resultante es entero y contiene a (2) que vincula todas las variables, las cotas que son buenas pero en
menor grado son las que se obtienen relajando sólo (1) o (2).

Si se hubiese relajado la restricción (2) como restricción complicante , el lagrangeano es:

N
P P
P N
P P
P
L(x, λ) = {Kj yj + cj tj } + βi zi + λj { wi xij − T yj − tj }
j=1 i=1 j=1 i=1

Con lo cual, el problema queda como:

θ(λ) = min L(x, λ)

N
P
s.a. xij + zi = 1, i = 1, . . . , P (1)
j=1
PN
tj ≤ Q, (3)
j=1

xij , yj , zi ∈ {0, 1} i = 1, . . . , P ; j = 1, . . . , N. (4)

Se resuelve entonces el problema:

w∗ = max θ(λ)
s.a. λ≥0

Otras relajaciones lagrangeanas también pueden ser válidas. Se otorgará puntaje en función de los argumentos respecto
a la elección de la relajación, formulaciones y cota.

Detalle del puntaje:

2 pts. por escribir el lagrangeano de una relajación.
2 pts. por escribir problema completo relajado, el cual tiene que ser una relajación que entregue una buena cota.
3 pts, por comentarios respecto a la relajación realizada, calidad de la cota y complejidad de la relajación resultante
b) (2 pts) El problema también puede ser visto como uno con variables complicantes. Postule cuáles pueden ser variables
complicantes y reescriba el problema en forma ordenada mostrando cómo la estructura se ajusta a la necesaria para
una Descomposición de Benders.

Solución: Las variables complicantes son xij , yj y zi ya que estas son variables enteras (binarias). Cualquier otra
elección de variables complicantes es equivocada ya que conllevarı́a a un problema satélite de Benders con variables
enteras y esto no puede ocurrir por definición de la descomposición.

Recordemos que la Descomposición de Benders aplica a un problema de la forma:

min cT x +dT y

s.a. Ax =b

Ex +Dy =e

x ∈ C, y ≥ 0

Para visualizar la descomposición de Benders, es útil ver el problema escrito de la siguiente forma:
N
P P
P N
P
min cT Kj yj + βi zi + dT cj t j
j=1 i=1 j=1
N
P
s.a. xij + zi =1 i = 1, . . . , P (1)
j=1 A b
PP
wi xij − T yj − tj ≤ 0 j = 1, . . . , N (2)
i=1
E DP
N e
tj ≤Q (3)
j=1

xij , yj , zi ∈ {0, 1}, tj ≥ 0 i = 1, . . . , P ; j = 1, . . . , N (4)

Por lo tanto, Ax = b corresponde a las restricción (1) donde las variables x de la Descomposición de Benders son las
variables xij , yj y zi en el problema original.

La matriz E de la Descomposición de Benders corresponde a la siguiente:

 
E
 2
0

P
P
donde E2 es la matriz definida por la parte wi xij − T yj de la restricción (2) y 0 es el vector nulo de dimensiones
i=1
1 × NP.

Por último, la matriz D es la definida por la parte −tj de la restricción (2) y la restricción (3).

Detalle del puntaje:

• 1 punto por identificar variables complicantes xij , yj y zi

 • 1 punto por mostrar la estructura adecuada para la Descomposición de Benders. (0/2 puntos si se identificaron
variables complicantes equivocadas)

c) (7 pts) Detalle los pasos para llevar adelante la Descomposición de Benders al problema. Debe explicitar el problema
satélite y el problema maestro, ası́ como explicar bien cómo se van generando los cortes para la resolución, siguiendo
el algoritmo de Benders. (Se calificarán 2 puntos por la formulación del maestro, 3 por el satélite, y 2 por los otros
detalles del algoritmo).

Solución: El problema interior es:

N
P
min cj tj
j=1
P
P
s.a. tj ≥ wi xij − T yj , j = 1, . . . , N (πj ) (P 1)
i=1
N
P
tj ≤ Q, (α) (P 2)
j=1

tj ≥ 0, j = 1, . . . , N. (P 3)

Al calcular el dual, resulta el problema satélite:

N
P P
P
max πj ( wi xij − T yj ) + Qα
j=1 i=1

s.a. πj + α ≤ cj j = 1, . . . , N (D1)
πj ≥ 0, α ≤ 0 j = 1, . . . , N. (D2)

El problema maestro de Benders para la iteración K es, entonces:

N P
z K = min
P P
K j yj + β i zi + γ
j=1 i=1
PN
s.a. xij + zi = 1, i = 1, . . . , P (M 1)
j=1
N P
πjl ( wi xij − T yj ) + Qαl ≤ γ,
P P
l = 1, . . . , Opt(K) (M 2 Opt.)
j=1 i=1
N P
fjh ( wi xij − T yj ) + Qg h ≤ 0
P P
h = 1, . . . , F act(K) (M 3 F act.)
j=1 i=1

xij , yj , zi ∈ {0, 1}, i = 1, . . . , P ; j = 1, . . . , N (M 4)

Es importante mencionar que en la formulación anterior, los πjl y αl son los valores fijos de las correspondientes variables
duales del problema satélite asociado al corte de optimalidad l. Notemos que no es posible asociar l directamente con
el número de iteración ya que es posible que hayan iteraciones donde no se hagan cortes de optimalidad (y, en cambio,
se hagan cortes de factibilidad). Los valores fjh y g h son los valores del rayo de escape rescatado del problema satélite
asociado al corte de factibilidad h. Se definen también Opt(K) y F act(K) que simbolizan la cantidad de cortes de
optimalidad y de factibilidad realizados hasta la iteración K respectivamente.
El problema satélite que genera los cortes tiene la siguiente forma en la iteración K:
N P
wK = max w i xK K
P P
πj ( ij − T yj ) + Qα
j=1 i=1

s.a. πj + α ≤ cj j = 1, . . . , N (D1)
πj ≥ 0, α ≤ 0 j = 1, . . . , N (D2)

Notemos que ahora las variables provenientes del problema maestro contienen un superı́ndice K ya que indican su valor
proveniente de z K . Notemos también que el problema satélite en su forma dual puede ser no acotado. Esto último se
puede ver directo de la formulación dual pero es más fácil ver que el primal puede ser infactible ya que puede que la
cota inferior de tj definida por (P 1) sea mayor que la cota superior de tj definida por (P 2), resultando en un problema
primal infactible y dual no acotado (ya que siempre es factible).

Los pasos del algoritmo son los siguientes:

k=0

1. Se resuelve el problema maestro obteniendo un vector solución (xk , y k , z k ) y se entrega esta solución al problema
satélite (puede entregar solamente (xk , y k )).

2. Se resuelve el problema satélite con los valores (xk , y k ). Existen tres casos posibles:

• El problema satélite es no acotado con rayo de escape hk = (f k , g k ), donde f se asocia con π y g con α. Se
agrega un corte de factibilidad al problema maestro del tipo:
N
X P
X
fjk ( wi xij − T yj ) + Qg k ≤ 0
j=1 i=1

• El problema satélite es acotado y se obtiene el valor óptimo wk . Sean (π k , αk ) los vectores duales. Si wk > γ k ,
entonces con la solución agregamos un corte de optimalidad al problema maestro del tipo:
N
X P
X
πjk ( wi xij − T yj ) + Qαk ≤ γ
j=1 i=1

• El problema satélite es acotado y se obtiene el valor óptimo wk . Si wk ≤ γ k , entonces hemos llegado al óptimo
y termina el algoritmo con solución óptima (xk , y k ).

3. Revisar condición de parada (para la corrección se consideran también aceptables condiciones como iteraciones
máximas, gap entre wk y γ k , etc). Se actualiza el problema maestro y se vuelve al paso 1. k = k + 1

Detalle del puntaje:

• 2 puntos por problema maestro (si puso solamente cortes de optimalidad 1/2).

• 3 puntos por problema satélite (en forma dual, si puso solamente el primal 1.5/3).

• 2 puntos por detalles del algoritmo (0.5 por cortes de optimalidad, 0.5 por cortes de factibilidad, 0.5 por condición
de término y 0.5 por comunicación correcta entre maestro y satélite a través de las variables)