المسرد · method
طريقة مستوي القطع
طريقة تشدد رخوة LP لبرنامج صحيح تكرارياً بمتباينات صالحة تحافظ على كل الحلول الصحيحة الممكنة بينما تقطع الأمثل الكسري لـ LP؛ قدمها Gomory (1958) للبرمجة الصحيحة.
Cutting Plane Methodقطع Gomoryمتباينات صالحةBranch-and-Cut
طريقة مستوي القطع (cutting plane method) تقنية كلاسيكية للبرمجة الصحيحة (IP) والبرمجة الصحيحة المختلطة (MIP) تشدد رخوة LP تكرارياً بـ **متباينات صالحة** تقطع الأمثل الكسري لـ LP دون استبعاد أي نقطة صحيحة ممكنة. قدمها Gomory (1958) للبرمجة الصحيحة (Gomory fractional cut) وGomory (1960) للنوع الصحيح المختلط (Gomory mixed-integer cut). تسير الخوارزمية كالتالي: حل رخوة LP؛ إذا كان الحل صحيحاً فالأمثل وُجد؛ خلاف ذلك يُولَّد قطع يستبعد النقطة الكسرية ويحافظ على كل النقاط الصحيحة الممكنة، يُضاف للنموذج، ويُعاد حل LP؛ تتكرر العملية حتى الصحة. عائلات القطع خاصة بالمسألة: قطع تغطية الحقيبة، قطع تغطية التدفق، قطع clique (تلوين الرسوم/IP)، تقريب صحيح مختلط (MIR)، قطع Chvátal-Gomory، قطع lift-and-project (Balas وCeria وCornuéjols 1993)، متباينات subtour وcomb لـ TSP (Padberg-Rinaldi 1991). لأن قطع Gomory الصرفة تتقارب ببطء عملياً، تجمع التطبيقات الحديثة القطع مع branch and bound (branch-and-cut، Padberg وRinaldi 1991) — البنية الأساس لـ solvers MIP الحديثة. توليد القطع آلي وشبه غير مرئي للمستخدم. Nemhauser وWolsey (1988)، Wolsey (1998)، وCornuéjols (2008) قراءات مرجعية.
Örnek
مُصنّع منسوجات منزلية متوسط الحجم في قيصري (إيرادات سنوية 32M USD) بـ 18 خط إنتاج و 240 SKU في مسألة جدولته الأسبوعية يحصل على فجوة 4.6% في 18 دقيقة من B&B الصرف؛ نفس النسخة تحت branch-and-cut الآلي تُغلق إلى فجوة 0.9% في 110 ثانية. تنتج شجرة القطع 6.300 قطع تغطية، 1.840 قطع MIR، و 420 قطع تغطية تدفق. التكلفة السنوية للإعداد والعمل الإضافي تنخفض بـ 1.4M TRY.