المسرد · approach
البرمجة الصحيحة (IP)
صنف من مسائل التحسين الخطي يُقيد فيه كل متغير قرار بقيم صحيحة؛ الفئة الفرعية الصحيحة البحتة من MILP، NP-صعب عموماً.
Integer ProgrammingIPالبرمجة الصحيحةInteger Linear ProgrammingILP
البرمجة الصحيحة (pure IP) هي صنف المسائل min c^T x s.t. Ax ≤ b, x ∈ Z^n_+ في الصورة القياسية، حيث جميع متغيرات القرار صحيحة. الحالة الخاصة 0-1 (الثنائية) x ∈ {0,1}^n هي الصياغة الطبيعية للتحسين التوافقي: حقيبة الظهر، الإسناد، تغطية المجموعات، تقسيم المجموعات، مسألة البائع المتجول (TSP)، التطابق، وتلوين الرسوم البيانية. التعقيد: تظهر pure IP بصيغة 0-1 IP في قائمة Karp (1972) للمسائل NP-كاملة الـ 21؛ أظهر Lenstra (1983) أن IP قابلة للحل في زمن متعدد الحدود ضمن بُعد ثابت (غير عملي عندما يكون البُعد جزءاً من المدخل). فرض الصحة على استرخاء LP يمكن أن يحرك القيمة المثلى بشكل حاد؛ وفجوة الصحة هي المقياس الكلاسيكي لقوة الصياغة. الخوارزمية الكلاسيكية هي طريقة مستويات القطع لـ Gomory (1958): حل استرخاء LP، إذا كان الأمثل كسرياً يولَّد قطع Gomory (باستخدام جدول السمبلكس) يستبعد الأمثل الحالي ولكنه لا يستبعد أي نقطة صحيحة ممكنة، يُضاف ويُعاد الحل؛ ينتهي عند الأمثل الصحيح بعدد منتهٍ من التكرارات (نظرياً). عملياً، فإن branch-and-bound لـ Land و Doig (1960) ثم branch-and-cut (Padberg و Rinaldi 1991) أسرع. تستنبط نظرية الأشكال متعددة السطوح — Chvátal (1973)، Schrijver (1986) — متباينات صحيحة (subtour-elimination، blossom للـ TSP) تقرب استرخاء LP من الغلاف المحدب للنقاط الصحيحة الممكنة. التطبيقات: TSP / توجيه المركبات (Dantzig و Fulkerson و Johnson 1954)، الإسناد، الجدولة، تدفق الشبكات، cutting stock (Gilmore و Gomory 1961)، bin packing.
Örnek
تحل أسطول توصيل من 22 مركبة في أنطاليا برنامجاً صحيحاً من نوع TSP لـ 65 زيارة يومية للعملاء: 4,225 متغيراً ثنائياً x_ij، نحو 8,500 قيد بما في ذلك إلغاء المسارات الفرعية؛ يعيد branch-and-cut بسريع البدء بإرشادي جيد حلاً ضمن فجوة 1.5% في 12 دقيقة، مخفضاً المسافة اليومية الإجمالية من 387 كم إلى 318 كم (نحو 18% توفير).