طريقة حدسية لمشكلة تغطية المجموعة

نقدم أسلوباً حدسياً يعتمد على اللاغرانج للمشكلة المعروفة بمشكلة تغطية المجموعة (SCP). تم تصميم الخوارزمية في البداية لحل حالات SCP كبيرة جداً، تشمل حتى 5,000 صف و1,000,000 عمود، ناتجة عن جدولة الطاقم في شركة السكك الحديدية الإيطالية، فيروفي ديلو ستاتو SpA. في عام 1994، نظمت شركة فيروفي ديلو ستاتو SpA، بالتعاون مع الجمعية الإيطالية للبحوث التشغيلية، مسابقة، أطلق عليها اسم FASTER، بهدف تعزيز تطوير الخوارزميات القادرة على إنتاج حلول جيدة لهذه الحالات، حيث تواجه الأساليب الكلاسيكية صعوبات كبيرة في التعامل معها. تتمثل الخصائص الرئيسية للخوارزمية التي نقترحها في (1) نظام تسعير ديناميكي للمتغيرات، مشابه لما يُستخدم لحل برامج LP الكبيرة، ليرتبط مع تحسينات تحت التدرج والخوارزميات الجشعة، و(2) الاستخدام المنهجي لتثبيت الأعمدة للحصول على حلول محسنة. علاوة على ذلك، نقترح عددًا من التحسينات على الطريقة القياسية لتحديد حجم الخطوة واتجاه الصعود ضمن إجراء تحسين التدرج الفرعي، والدرجات ضمن الخوارزميات الجشعة. أخيراً، يُقترح إجراء تنقية فعال. حصل برنامجنا على الجائزة الأولى في مسابقة FASTER، مقدماً أفضل قيمة للحل لجميع الحالات المقترحة. تم أيضًا اختبار الخوارزمية على الحالات الاختبارية من الأدبيات: في 92 من أصل 94 حالة في مجموعة الاختبار لدينا، وجدنا، في فترة حساب قصيرة، الحل الأمثل (أو المعروف الأفضل). علاوة على ذلك، من بين 18 حالة لا يُعرف فيها الحل الأمثل، في 6 حالات كان حلنا أفضل من أي حل آخر وجدته التقنيات السابقة.