دراسة تأثير موازاة خوارزميات التفرع و الحد (Bound & Branch) في تحسين أدائها

تستخدم خوارزميات التفرع و الحد (Bound and Branch) التي يرمز لها بـ B&B في حل مـسائل الأمثلة (الاستمثال) التوافقية التي تصنف درجة تعقيدها في الفئة hard-NP . و على الرغم من فعالية هذه الخوارزميات فقد بقي حجم المسائل التي تتمكن من حلها و البرهان على أمثلة الحـل محـدوداً بـسبب محدودية قدرات الحواسيب رغم تطورها الكبير. و مع ظهور البرمجة المتوازية و الحواسيب متعددة المعالجات فكر الباحثون بالاستفادة من قدرات هذه التقانات و الأجهزة في زيادة حجم المسائل المحلولة إلا أنه نجم عن الموازاة ثلاثة أنـواع مختلفـة مـن الشذوذ. يهدف هذا البحث إلى تقديم نموذج جديد لخوارزمية التفرع و الحد المتوازية يسمح بتحليـل فعاليـات الخوارزمية و يستند هذا النموذج إلى قواعد جديدة للاختيار بين العقد المتساوية التقويم بعد أن ثبت عجز قاعدة اختيار العقدة ذات التقويم الأفضل، كما نقوم بحساب حدود محكمة لكل قاعدة من القواعد و نبـرهن على إمكانية بلوغها، كما نقدم الشروط اللازمة و الكافية لظهور كل حالة من حالات الشذوذ النـاجم عـن موازاة الخوارزمية. درسنا و قارنا في هذا البحث النتائج الناجمة عن تجاهل بعض الفرضيات المستخدمة في خوارزميـات التفرع و الحد، و اقترحنا فضلاً عن ذلك استخدام النماذج غير المتزامنة للاستفادة القصوى من الإمكانيـات التي تقدمها البرمجة المتوازية.

The Branch and Bound algorithms which are refereed to as B & B are commonly used to solve NP - hard combinatorial optimization problems. Although these algorithms were efficient, the size of problems which can solved and proved the optimality of solution by these algorithms was limited, because of the limitation of computers capabilities although of it’s highly development. When the parallel programming 46 and Multiprocessors computers were appeared, the researcher thought to use the capabilities of these techniques and machines to increase the size of solved problems. Three main anomalies may occur when the parallelism is used. This research aimed to design a new model of Branch and Bound algorithms in order to analyze the performance. This model based on a new rule to choose the best node among the equal evaluation node. Tight bounds of each rules were computed and proved the ability to achieve it. Sufficient and necessary condition anomalous are given regarding the predisposition for each of the three classes of behavior. In this research, we discussed and compared the results of further relaxations on the assumptions used in branch and bound algorithms. We suggested using the asynchronous models to have the utmost benefit of the capabilities of parallel programming.