Rilassamento Lagrangiano

Il rilassamento lagrangiano è una tecnica classica di decomposizione che riduce un problema di ottimizzazione con vincoli strutturali duri a un sottoproblema più facile dualizzando i vincoli complicanti tramite moltiplicatori di Lagrange che penalizzano la loro violazione nella funzione obiettivo. L'uso sistematico in RO è iniziato con il rilassamento 1-tree di Held e Karp (1970, 1971) per il commesso viaggiatore, è stato collocato nel framework MIP generale da Geoffrion (1974) e popolarizzato tra i professionisti dall'articolo handbook di Fisher (1981). Nel problema min c·x : A₁x = b₁, A₂x = b₂, x ∈ X, se A₁x = b₁ è difficile, i moltiplicatori λ lo dualizzano: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — tipicamente questo si decompone in strutture di zaino, assegnamento o cammino minimo risolvibili in tempo polinomiale. Il duale lagrangiano max_λ L(λ) fornisce un bound lagrangiano che non è mai peggiore del bound LP e il cui gap di dualità debole è limitato dal gap di interezza del problema. Per risolvere il duale si usano il metodo del subgradiente (Held, Wolfe e Crowder 1974), i metodi bundle (Lemaréchal 1975) o l'algoritmo del volume (Barahona e Anbil 2000). Il rilassamento lagrangiano si usa per generare bound primali e stringere i bound dentro branch and bound su GAP, set covering, MCNF, localizzazione capacitata e scheduling. Wolsey (1998) capitolo 10 è il riferimento standard.