Branch-and-Cut

Branch-and-cut هو إطار الحلّ الـexact للبرمجة العددية الصحيحة المختلطة (MIP) الذي يكمن في كلّ حلّال MIP حديث تجاري أو مفتوح المصدر. يجمع فكرتين: (أ) **branch-and-bound** — تقسيم المسألة العددية إلى مسائل فرعية أصغر عبر تفريع المتغيّرات، حلّ ارتخاء الـLP في كلّ عقدة، وتقليم الأشجار الفرعية التي يكون حدّها LP أسوأ من أفضل حلّ ممكن حاليّ؛ (ب) **القطوع** — قبل التفريع، إضافة متراجحات صحيحة (قطوع) يستوفيها كلّ حلّ عددي ممكن لكنّها تقطع الـoptimum LP الكسري الحالي، فتشدّ الارتخاء وتضيّق فجوة الحدّ. أدخل هذه المقاربة Dantzig وFulkerson وJohnson (1954) على Travelling Salesman Problem (TSP) — استعملوا قطوع إلغاء الجولات الفرعية ضمن بحث branch-and-bound وحلّوا نسخة من 49 مدينة exact إلى الـoptimum. عمّم Padberg وRinaldi (1991) الإطار بإجراءات فصل تكتشف القطوع المنتهكة على الطيران. اليوم branch-and-cut هو الأسلوب الـexact الافتراضي لـTSP وVRP والجدولة وتموضع المنشآت وعشرات مسائل التحسين التركيبي الأخرى؛ أداء الحلّال المُبلّغ على TSP تجاوز 85K+ عقدة (Applegate وBixby وChvátal وCook 2006). القطوع المستخدمة عمليًا: إلغاء الجولات الفرعية، متراجحات الـcomb، قطوع الـclique، قطوع Gomory، قطوع التقريب العددي المختلط، قطوع lift-and-project.