التفرع والتحديد

التفرع والتحديد (branch and bound، B&B) هو طريقة الحل الدقيق القياسية للبرمجة العددية الصحيحة المختلطة (MIP) والعديد من مسائل التحسين المنفصلة. قدمها Land وDoig (1960) لـ MIP، طبّقها Little وآخرون (1963) على TSP، ووضّح Dakin (1965) قاعدة التفرع للقيود الصحيحة. تقسّم الخوارزمية المنطقة الممكنة تكرارياً إلى مناطق فرعية (تفرع — مثلاً لمتغير صحيح x بقيمة x* كسرية، طفلين x ≤ ⌊x*⌋ و x ≥ ⌈x*⌉)، تحل **رخوة LP** عند كل عقدة للحصول على حد أدنى (في التصغير)، تحافظ على حد أعلى عبر أفضل حل صحيح ممكن وُجد (incumbent)، **تقلّم بالحد** أي عقدة حدها LP ليس أفضل من incumbent، **تقلّم بالصحة** عندما يكون حل LP صحيحاً بالفعل، وترفض العقد غير الممكنة. عند استنفاد الشجرة، يكون incumbent هو الأمثل العام. Branch-and-cut (Padberg وRinaldi 1991) يقرن B&B بمستويات القطع وهو العمود الفقري لـ solvers MIP الحديثة. Branch-and-price (Barnhart وآخرون 1998) يقرنه بتوليد الأعمدة ويحل صياغات ضخمة. استراتيجية التفرع (most-fractional، strong branching، pseudocost branching)، اختيار العقدة (best-first، depth-first، best-estimate)، والمعالجة المسبقة تؤثر بشكل دراماتيكي على الأداء. Wolsey (1998) *Integer Programming* وNemhauser وWolsey (1988) مراجع قياسية. solvers MIP الحديثة تتعامل مع مسائل بـ 100M متغير عبر تركيبة B&B + قطوع + إرشاديات.