engleski

Parallel implementation of the combined algorithm of the branch and bound method

Parallel implementation of a combined branch-and-bound algorithm for the knapsack problem are considered. An approach combining parallel implementations of the branch-and-bound method and the heuristic search is proposed and implemented. Basic attention is focused on the questions of research of efficiency and acceleration for calculations due to the increase of the cluster system knots. As a result of the proposed approach, a organization scheme of the combined algorithm of distributed computing was obtained. The approach proposed in this studies saves the developers’ efforts by reapplying common parts of the algorithm to solve various problems of optimization. In fact, one can implement a common solution scheme for different platforms once, and later use only problem-dependent modules for a specific class of problems.

branch method ; bound method ; parallel implementation ; knapsack problem

The conference was canceled due the low number of presenters registered for the conference, but the Book of abstracts has been published.