Multi-thread Based Parallel Branch And Bound Algorithm Framework And Its Application

With the rapid development of information technology industry, multi-core processors become mainstream products. It is a tendency in program development that developing parallel programs and utilizing multiple core in multi-core processors adequately. As the core of a parallel program development, parallel algorithm has become a new research direction. However, due to the design and implementation of parallel algorithms has always complicated So, it has practical significance to research a parallel algorithm framework which is versatility.We study the commonly used branch and bound algorithms that to solve the optimization problems, and divided it into the part that associated with problem and the irrelevant one. And then, designed a multi-thread based parallel branch and bound algorithm framework. Using parallel branch and bound algorithm framework calculate the problem of slab outbound, and we conduct extensive experiments to verify the effectiveness and efficiency of our proposed algorithm framework.There have three modules in multi-thread based parallel branch and bound algorithm framework. They are node definition module, dependent interface module and parallel branch and bound algorithm module. Node definition module and dependent interface module is the part that associated with problems. It is needed to define the node types and relevant interface functions in these two modules, when the developers using the framework to solve specific problems. Parallel branch and bound algorithm module is the core of parallel branch and bound algorithm, it is the part that irrelevant with problems. It mainly content is parallel environment parameters setting, parallel branch and bound algorithm, and so on. The developers need not to edit the content of the module when using the framework.In conclusion, we proposed a multi-thread based parallel branch and bound algorithm framework. It adopts the Win32 API in Windows multithreaded programming technology to realize the algorithm parallelization, so as to improve the CPU usage effectively. Using the parallel branch and bound algorithm framework to solve the problem could improve the algorithm design reutilization and reduce the developers’workload. In a word, the framework has a certain practical application value.