الانتقال إلى المحتوى
العودة إلى نتائج البحث

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

قدّمه
Ailsa Land & Alison Doig
السنة
1960
النوع
Exact combinatorial optimization algorithm
العائلة
Mathematical programming

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

التفرع والتحديد هو خوارزمية دقيقة منهجية لمشاكل التحسين التوافقي والصحيح، قدمتها أليسا لاند وأليسون دويغ في عام 1960. تنظم مساحة البحث كشجرة من المشاكل الفرعية، وتستخدم حدودًا عليا مشتقة من الاسترخاء لتقليم الفروع التي لا يمكنها تحسين أفضل حل معروف، وتضمن إيجاد حل صحيح أمثل عالميًا. إنها العمود الفقري لحلول البرمجة الصحيحة المختلطة الحديثة المستخدمة في بحوث العمليات، واللوجستيات، والجدولة، والتصميم الهندسي.

الفكرة الحدسية وراء الطريقة

تخيل البحث عن العنصر الأعلى قيمة المخفي في متاهة واسعة من الغرف. بدلاً من فحص كل غرفة، تقدر الحد الأقصى للقيمة الممكنة التي يمكن الوصول إليها من كل ممر قبل دخوله. إذا كان هذا السقف أقل من أفضل عنصر لديك بالفعل، فإنك تتخطى الممر بأكمله دون النظر إليه. يعمل التفرع والتحديد بنفس الطريقة: فهو يقسم المشكلة إلى أجزاء أصغر، ويحسب حدودًا عليا متفائلة لكل جزء، ويتخلص فورًا من أي جزء لا يمكنه إثبات أنه يتفوق على أفضل حل حالي.

التاريخ

نشر لاند ودويغ الورقة الأساسية للتفرع والتحديد في مجلة Econometrica عام 1960، واصفين إياها كطريقة آلية للبرمجة المنفصلة. طبق ليتل وآخرون (1963) التقنية على مشكلة البائع المتجول، مما عزز دورها في التحسين التوافقي. قدم داكين (1965) تفرع استرخاء البرمجة الخطية، وهو الشكل الأكثر استخدامًا اليوم. شهدت العقود اللاحقة دمج مستويات القطع (التفرع والقطع) وتوليد الأعمدة (التفرع والسعر)، مما جعل التفرع والتحديد المحرك داخل جميع حلول البرمجة الصحيحة التجارية الرئيسية.

متى تُستخدم

استخدم التفرع والتحديد عندما يجب عليك العثور على الحل الأمثل المثبت لبرنامج خطي صحيح مختلط أو صحيح بحت ولا يمكنك قبول إجابة تقريبية. يفترض أن المشكلة يمكن صياغتها باستخدام استرخاءات خطية (أو محدبة) توفر حدودًا مفيدة. إنها أقل ملاءمة للحالات الكبيرة جدًا حيث تنفجر شجرة التعداد، ولبرامج التحسين غير الخطية الصحيحة بدون استرخاءات ضيقة، أو للإعدادات في الوقت الفعلي حيث يكون وقت الحساب محدودًا للغاية. في مثل هذه الحالات، قد يُفضل استخدام الاستدلالات أو الاستدلالات الفوقية.

الحدود والاعتبارات

  • التعقيد في أسوأ الحالات أسي؛ في الحالات سيئة الهيكلة يمكن أن تنمو الشجرة بشكل كبير بشكل غير عملي.
  • يعتمد الأداء بشكل كبير على اختيار متغير التفرع واستراتيجية اختيار العقدة.
  • يتطلب استرخاءً قابلاً للمعالجة يوفر حدودًا عليا ذات مغزى؛ الحدود الضعيفة تؤدي إلى تقليم ضئيل.
  • يمكن أن تكون متطلبات الذاكرة كبيرة عندما يجب تخزين العديد من العقد المفتوحة في وقت واحد.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • يضمن الأمثل العالمي للبرامج الصحيحة والتوافقية.
  • يقلل البحث بشكل كبير من خلال التقليم المستند إلى الحدود - غالبًا ما يتم استكشاف جزء صغير فقط من شجرة التعداد الكاملة.
  • مرن: يمكنه دمج مستويات القطع (التفرع والقطع) أو الحدود الاستدلالية (التفرع والسعر) لمزيد من الكفاءة.
  • مطبق على نطاق واسع في الحلول التجارية الناضجة (CPLEX، Gurobi) والأدوات مفتوحة المصدر (GLPK، CBC).

التطبيقات

  • جدولة طواقم الطائرات وتخصيص الأساطيل في بحوث العمليات.
  • تصميم شبكات سلسلة التوريد ومشاكل تحديد المواقع.
  • تخطيط دوائر VLSI وتخصيص السجلات في هندسة الحاسوب.
  • التنبؤ ببنية البروتين وتجميع الجينوم في البيولوجيا الحاسوبية.
  • تحسين المحافظ المالية مع قيود العدد.

كيف يعمل

كيف يعمل

1

تبدأ الخوارزمية بحل نسخة مسترخية من المشكلة - عادةً استرخاء البرمجة الخطية - التي تتجاهل قيود التكامل. يوفر هذا الاسترخاء حدًا علويًا للقيمة المثلى الحقيقية لأن كل حل صحيح ممكن هو أيضًا حل ممكن في الاسترخاء. إذا كان الحل المسترخي عدديًا صحيحًا بالصدفة، يتم حل المشكلة على الفور.

الصيغة
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

عندما يحتوي الحل المسترخي على متغير كسري، تقوم الخوارزمية بتقسيم المنطقة الممكنة عن طريق إضافة قيود تكميلية تجبر المتغير إما على أرضيته أو سقفه. ينشئ كل قسم عقدة ابن جديدة في شجرة البحث، مما يقسم فعليًا مشكلة فرعية واحدة إلى مشكلتين فرعيتين أصغر بنطاقات أضيق.

الصيغة
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

تتلقى كل عقدة نشطة حد استرخاء البرمجة الخطية الخاص بها. العقدة التي لا يتجاوز حدها أفضل حل صحيح تم العثور عليه حتى الآن - يسمى الحاضن - لا يمكن أن تحتوي على حل أفضل، لذلك يتم تقليمها. الحدود الضيقة أمر بالغ الأهمية: كلما كان الحد أضيق، قل عدد العقد التي تحتاج إلى استكشافها.

الصيغة
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

يتم استبعاد العقدة (إغلاقها بشكل دائم) تحت ثلاثة شروط: استرخاؤها غير ممكن، أو حدها ليس أفضل من الحاضن، أو حلها المسترخي بالفعل ممكن عدديًا بشكل صحيح. في الحالة الأخيرة، يتم تحديث الحاضن إذا كان الحل الجديد يحسنه. تنتهي الخوارزمية عندما يتم استبعاد جميع العقد، وعند هذه النقطة يكون الحاضن هو الأمثل العالمي.

الصيغة
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

الأخطاء الشائعة

  • اختيار متغير التفرع بشكل سيء (على سبيل المثال، التفرع دائمًا على المتغير الكسري الأول) يؤدي غالبًا إلى أشجار عميقة وغير متوازنة وتقارب بطيء.
  • تجاهل المتباينات الصالحة (مستويات القطع) يعني تفويت فرصة تشديد حدود الاسترخاء بشكل كبير.
  • الإنهاء المبكر بفجوة دون أمثلية لا يتم الإبلاغ عنها على هذا النحو يمكن أن يضلل الممارسين في اعتبار الحل شبه الأمثل حلاً دقيقًا.
  • قد يؤدي تطبيق التفرع والتحديد على استرخاءات غير خطية أو غير محدبة بدون تقويس متخصص إلى حدود غير صالحة ونتائج غير صحيحة.

الأسئلة الشائعة

كيف يختلف التفرع والتحديد عن التعداد الشامل؟

يقوم التعداد الشامل بتقييم كل حل صحيح ممكن بشكل صريح، وهو أمر غير ممكن حسابيًا للمشاكل الكبيرة. يتجنب التفرع والتحديد ذلك عن طريق حساب حدود عليا مستندة إلى الاسترخاء في كل عقدة من شجرة البحث وتقليم أشجار فرعية كاملة كلما لم يتمكن الحد من تجاوز أفضل حل تم العثور عليه بالفعل. في الممارسة العملية، يتم فحص جزء صغير فقط من الشجرة على الإطلاق.

ما هو دور استرخاء البرمجة الخطية في التفرع والتحديد؟

يسقط استرخاء البرمجة الخطية قيود التكامل، مما يجعل المشكلة قابلة للحل في وقت متعدد الحدود بواسطة طريقة السمبلكس أو طريقة النقطة الداخلية. قيمتها المثلى تعمل كحد أعلى للمشكلة الفرعية الصحيحة المقابلة. عندما يكون هذا الحد ضيقًا - قريبًا من الأمثل الصحيح الحقيقي - يتم استكشاف عدد أقل من الفروع. الاسترخاءات الأضيق، التي يتم تحقيقها غالبًا عن طريق إضافة متباينات صالحة، تسرع بشكل كبير الخوارزمية الشاملة.

متى يجب أن أستخدم التفرع والتحديد مقابل استدلال فوقي مثل الخوارزميات الجينية؟

اختر التفرع والتحديد عندما تحتاج إلى شهادة أمثلية ويمكنك تحمل وقت الحساب. إنه مثالي للمشاكل متوسطة الحجم ذات استرخاءات البرمجة الخطية جيدة الهيكلة. الاستدلالات الفوقية مفضلة عندما تكون المشكلة كبيرة جدًا، وتفتقر إلى استرخاء مفيد، أو يجب حلها ضمن ميزانية زمنية ضيقة حيث يكون الحل شبه الأمثل مقبولاً. يجمع العديد من الممارسين بين الاثنين: استخدم التفرع والتحديد مع تحمل فجوة إنهاء مبكر.

طرق ذات صلة

المصادر

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    افتح مرجع DOI
    تم النسخ.