Relajación de lagrange

Relajaci´n de Lagrange o
Considere el siguiente programa entero: (P:) z = max cx s.a : Ax Dx x ≤ b ≤ e ≥ 0, entero (1) (2) (3) (4)

Suponga que 2 es un conjunto de restricciones que complica elproblema.  u1  u2    Sea: u =  u3  un vector de m multiplicadores no-negativos u    ...  um (uno por cada restricci´n en 2). o

Relajaci´n de Lagrange o

Considere b − Ax ≥ 0 y u ≥ 0.u(b − Ax) ≥ 0 se cumple cuando 2 se satisface. Como 2 complican el problema, se remueven del conjunto de restricciones y se a˜aden al objetivo. n 1 se vuelve: z = m´x cx + u(b − Ax) a y el problema es:z s.a : Dx x

= max cx + u(b − Ax) ≤ e ≥ 0, entero

Relajaci´n de Lagrange o
(L:) z s.a : Dx x Beneficios: 1. El conjunto de restricciones 6 es m´s f´cil de tratar a a 2. Si 2 se satisfacen,se premia el objetivo. De lo contrario, se penaliza.
La penalizaci´n por no satisfacer 2 est´ dada por u o a un se puede ajustar de acuerdo con el grado de dificultad de la restricci´n n o

= max cx+ u(b − Ax) ≤ e ≥ 0, entero

(5) (6) (7)

La soluci´n de (L) es una cota superior a la soluci´n de (P) o o

Relajaci´n de Lagrange o
Si u es demasiado grande, Ax ≤ b estar´ sub-satisfecho yno a generar´ una buena soluci´n de (P). a o Si u es demasiado peque˜o, Ax ≤ b puede no satisfacerse en n absoluto u debe ser tal que: m´ m´x{cx + u(b − Ax)} ın a
u x

s.a : Dx x

≤ e ≥ 0, enteroAplicamos un m´todo iterativo para encontrar valores de u e que inducen x tal que se satisfacen las restricciones relajadas y se alcanza un buen valor objetivo del problema original.

Relajaci´nde Lagrange o

Problemas: ¿Qu´ restricciones relajar? e ¿Cu´l debe ser la penalizaci´n u? a o (L) debe producir una buena soluci´n factible de (P). o Se trata de encontrar el mejor conjunto de us,no de a˜adir n variables de penalizaci´n. o

Ejemplo, Relajaci´n de Lagrange o

z = max 16x1 + 10x2 + 4x4 s.a : 8x1 + 2x2 + x3 + 4x4 ≤ 10 x1 + x2 ≤ 1 x3 + x4 ≤ 1 xi binario ∀i ”Dualizando”9:...