PARALLEL IMPLEMENTATION OF THE COMBINED ALGORITHM OF THE BRANCH AND BOUND METHOD

Authors

  • Valeriy Ivaschenko
  • Gennady Shvachych
  • Vladimir Konovalenkov
  • Vladimir Khristyan

DOI:

https://doi.org/10.34185/1991-7848.itmm.2020.01.045

Keywords:

PERSONAL PERSONALIZED CALCULABLE CLUSTER, PARALLEL COMPUTING, BRANCH-AND-BOUND METHOD, KNAPSACK PROBLEM, LOCAL OPTIMIZATION

Abstract

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 paper 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.

References

V.P. Ivaschenko Improving the efficiency of the multiprocessor system through inline interface network aggregation / V.P. Ivaschenko, G.G. Shvachych, E.V. Ivaschenko,

V.V. Busygin // System technologies. N 2 (115) - Dnipro, 2018.- P.84-92.

Ivaschenko V.P. Effective algorithms for solving the transient coefficient of high accuracy order / V.P. Ivaschenko, G.G. Shvachych, E.V. Ivaschenko, V.V. Busygin // System technologies. N 4 (117) - Dnipro, 2018.- P.86 - 94. 4.

Downloads

Published

2020-03-26

Issue

Section

Статті