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 s
olution 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.
في المشكلة التي نعالجها, تحتاج شركة اتصالات إلى بناء مجموعة من الأبراج الخلوية لتوفير خدمة الاتصالات الخليوية للسكان في منطقة جغرافية. تم تحديد عدد من المواقع المحتملة لبناء الأبراج. يعتم اختيار هذه المواقع على عدة عوامل ، بما في ذلك مدى اتساق البرج
مع البيئة المحيطة وارتفاع التضاريس, تتمتع الأبراج بمدى تغطية ثابت ، وبسبب قيود الميزانية ، لا يمكن بناء سوى عدد محدود منها . بالنظر إلى هذه القيود ، ترغب الشركة في توفير تغطية لأكبر قدر ممكن من السكان, والهدف هو اختيار في أي من المواقع المحتملة يجب أن تقوم الشركة ببناء الأبراج.
إن المشكلة التي شرحناها يمكن نمذجتها لتصبح أحد أمثلة مشكلة 0/1 knapsack الشهيرة لذلك شرحنا في الحلقة مفهوم مشكلة 0/1 Knapsack والطرق المستخدمة في الحل, وتوسعنا في الشرح عن خوارزمية Branch and Bound كونها تعتبر أفضلها.
