المسرد · method
إرخاء لاغرانج
تقنية تحليل تنقل القيود المعقدة إلى دالة الهدف عبر مضاعفات لاغرانج وتختزل المسألة الفرعية المُرخاة إلى بنية سهلة؛ منهجها Held وKarp (1970) على TSP.
Lagrangian Relaxationثنائية لاغرانجحد Held-Karpطريقة Subgradient
إرخاء لاغرانج (Lagrangian relaxation) تقنية تحليل كلاسيكية تختزل مسألة تحسين ذات قيود هيكلية صعبة إلى مسألة فرعية أسهل عبر تثنية القيود المعقدة بمضاعفات لاغرانج تعاقب انتهاكها في دالة الهدف. بدأ الاستخدام المنهجي في بحوث العمليات بإرخاء 1-tree لـ Held وKarp (1970، 1971) للبائع المتجول، ووضعه Geoffrion (1974) في إطار MIP العام، وعممه Fisher (1981) في مقال handbook على الممارسين. في مسألة min c·x : A₁x = b₁, A₂x = b₂, x ∈ X، إذا كانت A₁x = b₁ صعبة، فإن المضاعفات λ تثنّيها: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — عادة تتفكك هذه المسألة الفرعية إلى هياكل حقيبة الظهر أو الإسناد أو أقصر مسار قابلة للحل في زمن كثير الحدود. ثنائي لاغرانج max_λ L(λ) يعطي حد لاغرانج لا يكون أبداً أسوأ من حد LP، وفجوة ثنائيته الضعيفة محدودة بفجوة الصحة للمسألة. لحل الثنائي تُستخدم طريقة subgradient (Held وWolfe وCrowder 1974)، طرق bundle (Lemaréchal 1975)، أو خوارزمية الحجم (Barahona وAnbil 2000). يُستخدم إرخاء لاغرانج لتوليد حدود ابتدائية وتشديد الحدود داخل branch and bound على GAP، set covering، MCNF، التموضع بطاقة، والجدولة. Wolsey (1998) الفصل 10 المرجع القياسي.
Örnek
تعاونية لوجستيات في تكيرداغ بـ 14 جراراً مختلفاً وتسليم يومي لـ 80 منطقة عميل ترخي VRP بطاقتها بتثنية قيود طاقة المركبات؛ تنهار كل شاحنة إلى TSP مستقل. في 28 ثانية يعطي الثنائي حداً ضمن فجوة 3.2%، متفوقاً على 4.1% التي حققها solver MIP منطلق بحد LP بعد 17 دقيقة. استخدام هذا الحد في branch and bound يسرّع مرحلة الحل بـ 42% ويترجم إلى 320.000 TRY تحسين تشغيلي سنوي.