Branch And Bound Algorithm For The Distribution Of Parallel Research

Branch and bound algorithm is an important method to be used to acquire the solution of optimal problems. But it needs too much time for getting the optimal solution, which extremely limits its role of practical application. In this thesis, the design and realization of a special cluster are presented for calculating branch and bound algorithm that can decrease the calculating time and enhance the algorithmic efficiency.Bases on analyzing the distributed parallel computing and other heuristic algorithms, the thesis focuses on how to decrease the time complexity of brand and bound algorithm in the special cluster mentioned above.The contents of thesis are as follows:1. Proposing a new accelerated mechanism for distributed parallel computing which can broadcast the present optimal value that is calculated by any computer in the cluster to others immediately.2. Presenting a modified branch and bound algorithm by adding the heuristic algorithm in the cluster which increasing the efficiency of eliminating node.3.The problem's scale is decreased through using distributed parallel computing algorithm.4. The TSP as benchmark shows that this cluster platform can increase the branch and bound algorithm's efficiency and get the optimal solution soon.