Trad 1

Relajación lagrangiana es una herramienta que se utiliza cada vez más, en las aplicaciones de programación matemática a gran escala como en los últimos años CPMS / TIMS ganador del Premio a la Gestión. En este tutorial, Marshall Fisher ofrece una guía práctica para la utilización del enfoque con muchos ejemplos e ilustraciones.
En la última década, la relajación lagrangiana ha pasado de ser unconcepto exitoso, pero en gran medida teórica, a una herramienta que es la columna vertebral de una serie de aplicaciones a gran escala. Aunque ha habido varios estudios sobre la relajación de Lagrange (por ejemplo, Fisher y Geoffrion y un tratamiento manual excelente, un mayor uso de la relajación de Lagrange en la práctica se ha visto obstaculizada por la falta de un "cómo hacerlo" exposiciónsimilar al tratamiento por lo general lineal otorgado, dinámico, y la programación de enteros en operaciones de textos de investigación. Este artículo se destina a llenar al menos parcialmente ese vacío y debe ser de interés para los desarrolladores y los usuarios de los algoritmos de relajación de Lagrange.
La relajación lagrangiana se basa en la observación de que muchos de los problemas deprogramación entera difíciles se pueden modelar como un problema relativamente fácil, complicado por un conjunto de restricciones laterales. Para explotar esta observación, creamos un problema de Lagrange en el que las limitaciones que complican se sustituyen por un término de penalización en la función objetivo que implica la cantidad de violación de las limitaciones y de sus variables duales. Elproblema de Lagrange es fácil de resolver y proporciona una cota superior (para un problema de maximización) sobre el valor óptimo del problema original. Por lo tanto, se puede utilizar en lugar de una relajación de programación lineal para proporcionar cotas en un algoritmo de branch and bound. El enfoque de Lagrange ofrece una serie de ventajas importantes sobre las relajaciones de programaciónlineal.
Lo primero será formular el concepto de relajación de Lagrange en términos generales y luego demostrar su uso en en un ejemplo numérico. Comienzo con un problema de programación entera de la siguiente forma:

 Z = max cx
     Ax <= b
    Dx <= e
 x> = 0 e integral,

donde x es n x 1, b es m x 1, e es k x 1 y todas las demás matrices tienen dimensiones acorde.
Suponemos que las limitaciones de(P) se han dividido en los dos conjuntos (ax <= b) y (Dx <= e) de modo que (P) es relativamente fácil de resolver si el conjunto de restricciones (ax <= b) es eliminado. Para crear el problema de Lagrange, primero definimos un vector m de multiplicadores no negativos u y añadimos el término no negativo u(b-Ax) a la función objetivo de (P) para obtener

max cx + u (b - Ax)
S.A: Ax <= b
      Dx <= e       x> = 0 e integral

Está claro que el valor óptimo de este problema para u, fijado en un valor no negativo, es una cota superior en Z porque simplemente hemos añadido un término no negativo a la función objetivo. En este punto, creamos el problema de Lagrange, eliminando las restricciones (Ax <= b) para obtener
 Zd (u) = cx max + u (b - Ax)
       dx <= e
       x> = 0 e integral

Dado que laeliminación de las restricciones (Ax <= b) no puede disminuir el valor óptimo, Zd (u) también es una cota superior en Z. Por otra parte, por supuesto el problema de Lagrange es relativamente fácil de resolver.
Hay tres grandes preguntas en el diseño de un sistema basado en el lagrangiano-relajación-:
(a) Que restricciones deben estar relajadas
(b) la forma de calcular los buenos multiplicadoresu
(c) la forma de deducir una buena solución, viable al problema original.
En términos generales, la respuesta a (a) es que la relajación debe hacer el problema mucho más fácil, pero no demasiado fácil.  Para (b) hay una elección entre un procedimiento objetivo general llamado el método subgradiente y métodos "más inteligentes" que puede ser mejor, pero que, sin embargo, altamente específico...