Lagrange Gevşemesi

Lagrange gevşemesi (Lagrangian relaxation), karmaşık kısıt yapısındaki bir optimizasyon problemini, ihlali Lagrange çarpanlarıyla amaç fonksiyonuna cezalandırılarak aktarılan zorlu kısıtların kaldırılmasıyla daha kolay alt-yapıya indirgeyen klasik bir ayrıştırma tekniğidir. Yöntemin OR'da sistematik kullanımı Held ve Karp'ın (1970, 1971) gezgin satıcı problemi (TSP) için 1-tree gevşemesi ile başlamış, Geoffrion'un (1974) ayrıştırma tartışmasıyla genel MIP çerçevesine yerleşmiş ve Fisher'ın (1981) handbook makalesi ile pratik uygulayıcı topluluğa açılmıştır. Min c·x : A₁x = b₁, A₂x = b₂, x ∈ X probleminde A₁x = b₁ kısıtları zor ise λ çarpanlarıyla aktarılır: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — bu alt-problem genelde knapsack, atama veya en kısa yol gibi polinom-zamanlı yapılara ayrışır. Lagrange duali max_λ L(λ) Lagrangian bound üretir; bu bound LP gevşeme bound'undan asla daha kötü değildir ve zayıf-dualite gap problem yapısı (integrality gap) tarafından sınırlandırılır. Lagrange dualinin çözümünde subgradient yöntemi (Held, Wolfe ve Crowder 1974), bundle methods (Lemaréchal 1975) ve volume algoritması (Barahona ve Anbil 2000) kullanılır. Lagrange gevşemesi GAP, set covering, MCNF, capacitated facility location ve scheduling problemlerinde primal bound üretimi ve branch-and-bound içinde sınır iyileştirme amaçlı kullanılır. Wolsey (1998) bölüm 10 standart referanstır.