الفرع والسعر
في الرياضيات التطبيقية ، تُعدّ طريقة التفرع والتسعير أسلوبًا من أساليب التحسين التوافقي لحلّ مسائل البرمجة الخطية الصحيحة (ILP) والبرمجة الخطية الصحيحة المختلطة (MILP) ذات المتغيرات المتعددة. وهي طريقة هجينة تجمع بين أسلوب التفرع والتقييد وأسلوب توليد الأعمدة .
وصف الخوارزمية
تُعدّ خوارزمية التفرع والتسعير إحدى طرق التفرع والتقييد، حيث يُمكن إضافة أعمدة إلى نموذج البرمجة الخطية المُبسّط (LP relax) عند كل عقدة في شجرة البحث. في بداية الخوارزمية، تُستبعد مجموعات من الأعمدة من نموذج البرمجة الخطية المُبسّط لتقليل متطلبات الحساب والذاكرة، ثم تُضاف الأعمدة مرة أخرى حسب الحاجة. يعتمد هذا النهج على ملاحظة أنه في المسائل الكبيرة، تكون معظم الأعمدة غير أساسية، ويكون المتغير المقابل لها مساويًا للصفر في أي حل أمثل. وبالتالي، فإن الغالبية العظمى من الأعمدة غير ذات صلة بحل المسألة.
تبدأ الخوارزمية عادةً بإعادة صياغة المسألة، مثل تفكيك دانتزيغ-وولف ، لتشكيل ما يُعرف بالمسألة الرئيسية . يُجرى التفكيك للحصول على صيغة للمسألة تُعطي حدودًا أفضل عند حلّها باستخدام طريقة الاسترخاء مقارنةً بحلّها باستخدام طريقة الاسترخاء للصيغة الأصلية. ولكن، نظرًا لأن التفكيك عادةً ما يحتوي على العديد من المتغيرات، يتم حلّ نسخة مُعدّلة، تُسمى المسألة الرئيسية المُقيّدة ، والتي لا تأخذ في الاعتبار سوى مجموعة فرعية من الأعمدة. [ 2 ] بعد ذلك، وللتحقق من الأمثلية، يتم حلّ مسألة فرعية تُسمى مسألة التسعير لإيجاد الأعمدة التي يُمكنها الدخول في الأساس وتقليل دالة الهدف (لمسألة تصغير). يتضمن ذلك إيجاد عمود ذي تكلفة مُخفّضة سالبة . تجدر الإشارة إلى أن مسألة التسعير نفسها قد تكون صعبة الحل، ولكن بما أنه ليس من الضروري إيجاد العمود ذي التكلفة المُخفّضة الأكثر سلبية، يُمكن استخدام طرق البحث الاستدلالية والمحلية. [ 3 ] يجب حلّ المسألة الفرعية بالكامل فقط لإثبات أن الحل الأمثل للمسألة الرئيسية المُقيّدة هو أيضًا حل أمثل للمسألة الرئيسية. في كل مرة يتم فيها العثور على عمود بتكلفة مخفضة سالبة، يُضاف إلى مسألة السيد المقيد ويُعاد تحسين عملية الاسترخاء. إذا لم يكن بالإمكان إدخال أي أعمدة في الأساس وكان حل الاسترخاء ليس عددًا صحيحًا، فسيحدث تفرع. [ 1 ]
تعتمد معظم خوارزميات التفرع والتسعير على طبيعة المشكلة، إذ يجب صياغة المشكلة بطريقة تسمح بصياغة قواعد تفرع فعالة، وتجعل حل مشكلة التسعير سهلاً نسبياً. [ 4 ]
إذا تم استخدام مستويات القطع لتضييق استرخاءات البرمجة الخطية داخل خوارزمية التفرع والتسعير، فإن الطريقة تُعرف باسم التفرع والتسعير والقطع . [ 5 ]
تطبيقات الفرع والسعر
يمكن استخدام طريقة التفرع والتسعير لحل المشكلات في مجموعة متنوعة من مجالات التطبيق، بما في ذلك:
- تلوين الرسوم البيانية متعدد الألوان. [ 3 ] يُعدّ هذا تعميمًا لمسألة تلوين الرسوم البيانية ، حيث يجب تخصيص عدد مُحدد مسبقًا من الألوان لكل عقدة في الرسم البياني، ولا يجوز أن تشترك أي عقدتين تشتركان في حافة واحدة في لون واحد. والهدف هو إيجاد الحد الأدنى لعدد الألوان اللازمة للحصول على تلوين صحيح. يمكن استخدام مسألة التلوين متعدد الألوان لنمذجة مجموعة متنوعة من التطبيقات، بما في ذلك جدولة المهام وتخصيص قنوات الاتصالات.
- مشاكل توجيه المركبات . [ 2 ]
- مشكلة التخصيص المعممة . [ 6 ]
انظر أيضاً
المراجع الخارجية
- شرائح عرض تقديمي حول الفروع والأسعار
- نموذج أولي لخوارزمية عامة للتفرع والتسعير
- الأسئلة الشائعة على موقع BranchAndCut.org
- SCIP هو إطار عمل مفتوح المصدر لتقنية تقسيم الفروع وتسعيرها، بالإضافة إلى برنامج لحل مسائل البرمجة الخطية المختلطة.
- أباكوس – نظام التفرع والقطع – برنامج مفتوح المصدر
مراجع
- 1 2 أكيلا، م.؛ س. غوبتا؛ أ. ساركار. "التفرع والسعر: توليد الأعمدة لحل برامج الأعداد الصحيحة الضخمة" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 21-08-2010 . تم الاطلاع عليه بتاريخ 19-12-2012 .
- 1 2 فييه، دومينيك (2010). "دليل تعليمي حول توليد الأعمدة وخوارزمية التفرع والتسعير لمسائل توجيه المركبات". 4OR . 8 (4): 407–424 . doi : 10.1007/s10288-010-0130-z .
- 1 2 مهروتا، أنوج؛ إم إيه تريك (2007). "نهج التفرع والتسعير لتلوين الرسوم البيانية المتعددة" . توسيع الآفاق: التطورات في الحوسبة، والتحسين، وتقنيات اتخاذ القرار . سلسلة واجهات بحوث العمليات/علوم الحاسوب. المجلد 37. الصفحات 15-29 . CiteSeerX 10.1.1.163.6870 . doi : 10.1007/978-0-387-48793-9_2 . ISBN 978-0-387-48790-8.
- ↑ جامراث، ج. "قطع الفروع وتسعيرها بشكل عام" (ملف PDF) .
- ↑ ديروسير، ج.؛ إم إي لوبيك (2010). "خوارزميات التسعير والقطع للفروع". موسوعة وايلي لبحوث العمليات وعلوم الإدارة .
- ↑ سافيلسبيرغ، م. (1997). "خوارزمية التفرع والتسعير لمسألة التخصيص المعممة". بحوث العمليات . 831-841. 45 (6): 831–841 . doi : 10.1287/opre.45.6.831 .
- بارنهارت، سينثيا؛ جونسون، إليس ل.؛ نيمهاوزر، جورج ل .؛ سافيلسبيرغ، مارتن دبليو بي؛ فانس، باميلا هـ. (1998)، "التفرع والتسعير: توليد الأعمدة لحل برامج الأعداد الصحيحة الضخمة"، بحوث العمليات ، 46 (3): 316-329 ، CiteSeerX 10.1.1.197.7390 ، doi : 10.1287/opre.46.3.316 ، JSTOR 222825
- التحسين التوافقي
- خوارزميات وأساليب التحسين