Glosario · method

Relajación Lagrangiana

Técnica de descomposición que traslada las restricciones complicantes a la función objetivo mediante multiplicadores de Lagrange y reduce el subproblema relajado a una estructura sencilla; sistematizada para TSP por Held y Karp (1970).

Lagrangian RelaxationDualidad LagrangianaCota de Held-KarpMétodo del Subgradiente

La relajación lagrangiana es una técnica clásica de descomposición que reduce un problema de optimización con restricciones estructurales duras a un subproblema más fácil mediante la dualización de las restricciones complicantes con multiplicadores de Lagrange que penalizan su violación en la función objetivo. Su uso sistemático en IO comenzó con la relajación de 1-árbol de Held y Karp (1970, 1971) para el problema del viajante, se ubicó en el marco MIP general por Geoffrion (1974) y fue popularizada entre profesionales por el artículo de Fisher (1981) en el handbook. En el problema min c·x : A₁x = b₁, A₂x = b₂, x ∈ X, si A₁x = b₁ es difícil, los multiplicadores λ lo dualizan: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — típicamente esto se descompone en estructuras de mochila, asignación o caminos mínimos resolubles en tiempo polinomial. El dual lagrangiano max_λ L(λ) rinde una cota lagrangiana que nunca es peor que la cota LP y cuyo gap de dualidad débil está acotado por el gap de integralidad del problema. Para resolver el dual se usa el método del subgradiente (Held, Wolfe y Crowder 1974), métodos bundle (Lemaréchal 1975) o el algoritmo del volumen (Barahona y Anbil 2000). La relajación lagrangiana se usa para generar cotas primales y apretar cotas dentro de branch and bound en GAP, set covering, MCNF, localización capacitada y scheduling. Wolsey (1998) capítulo 10 es la referencia estándar.

Örnek

Una cooperativa logística en Tekirdağ con 14 tractores distintos y entrega diaria a 80 zonas de clientes relaja su VRP capacitado dualizando las restricciones de capacidad vehicular; cada camión colapsa a un TSP independiente. En 28 segundos el dual entrega una cota dentro de un gap del 3,2%, batiendo el 4,1% logrado por un solver MIP arrancado en caliente con cota LP a los 17 minutos. Usar esta cota en branch and bound acelera la fase de resolución un 42% y se traduce en 320.000 TRY anuales de mejora operativa.