فجوة الأمثلية

تقيس فجوة الأمثلية المسافة بين قيمة أفضل حل ممكن تم العثور عليه (الحد الأعلى UB في التصغير) وأفضل حد مزدوج تم الحصول عليه حتى الآن (الحد الأدنى LB)؛ يوجد تعريفان قياسيان. الفجوة المطلقة = |UB - LB|. الفجوة النسبية (المتغير الكلاسيكي في MILP) = |UB - LB| / max(ε, |UB|)، أو في بعض الحلول |UB - LB| / max(ε, |LB|) — يختلف اختيار المقام حسب المورد، مع ε لحماية القسمة على صفر. فجوة صفرية تشهد بأن incumbent مثلى وتنهي الخوارزمية؛ عملياً، تتوقف الحلول مع علم 'شبه مثلى' عند هبوط الفجوة دون تسامح محدد من المستخدم (عادة 0.01-1%). الأساس المنطقي هو نظرية الازدواجية: في LP تعطي الازدواجية الضعيفة UB ≥ LB لكل زوج أولي-مزدوج ممكن، والازدواجية القوية تحول هذه المتباينة إلى مساواة. في MILP، يُنتج استرخاء LP الحد LB، ويحدّث branch-and-bound حد LB من عقدة لأخرى، وتحدّث الإرشاديات الأولية واستكشاف التفريع الحد UB. التفسير: فجوة 5% تعني 'قيمة الحل أسوأ بنسبة 5% على الأكثر من الأمثل' — لا يمكن رياضياً تحسين أدنى من LB المعروف. الاستخدامات العملية: إبلاغ المخاطر للإدارة (أسوأ حالة)، قرارات الإنهاء المبكر (مقايضة الوقت-الجودة في عمليات branch-and-cut الطويلة)، ومقارنة الإرشاديات. فجوة ازدواجية لاغرانج في البرمجة غير الخطية المحدبة وفجوة الاسترخاء في غير المحدبة مفاهيم مماثلة. مراجع كلاسيكية: Nemhauser و Wolsey (1988) و Wolsey (1998).