Geodesic
On а recursive-parallel algorithm for solving the Knapsack Problem
Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 2, pp. 155-164 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we offer an efficient parallel algorithm for solving the NP-complete Knapsack Problem in its basic, so-called 0-1 variant. To find its exact solution, algorithms belonging to the category "branch and bound methods” have long been used. To speed up the solving with varying degrees of efficiency, various options for parallelizing computations are also used. We propose here an algorithm for solving the problem, based on the paradigm of recursive-parallel computations. We consider it suited well for problems of this kind, when it is difficult to immediately break up the computations into a sufficient number of subtasks that are comparable in complexity, since they appear dynamically at run time. We used the RPM ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.
Keywords: Knapsack Problem, parallel algorithm, recursion
Mots-clés : .NET. 
@article{MAIS_2018_25_2_a0,
     author = {V. V. Vasilchikov},
     title = {On {\cyra} recursive-parallel algorithm for solving the {Knapsack} {Problem}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {155--164},
     year = {2018},
     volume = {25},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2018_25_2_a0/}
}
TY  - JOUR
AU  - V. V. Vasilchikov
TI  - On а recursive-parallel algorithm for solving the Knapsack Problem
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2018
SP  - 155
EP  - 164
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MAIS_2018_25_2_a0/
LA  - ru
ID  - MAIS_2018_25_2_a0
ER  - 
%0 Journal Article
%A V. V. Vasilchikov
%T On а recursive-parallel algorithm for solving the Knapsack Problem
%J Modelirovanie i analiz informacionnyh sistem
%D 2018
%P 155-164
%V 25
%N 2
%U http://geodesic.mathdoc.fr/item/MAIS_2018_25_2_a0/
%G ru
%F MAIS_2018_25_2_a0
V. V. Vasilchikov. On а recursive-parallel algorithm for solving the Knapsack Problem. Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 2, pp. 155-164. http://geodesic.mathdoc.fr/item/MAIS_2018_25_2_a0/

[1] Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co, San Francisco, 1979 | MR | MR

[2] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, Berlin, 2004 | MR

[3] Martello S., Toth P., Knapsack Problems Algorithms and Computer Implementation, Wiley, New York, 1990 | MR

[4] Cormen T., Leiserson Ch., Rivest R., Stein C., Introduction to Algorithms, The MIT Press, 2001 | MR

[5] Land A. H., Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520 | DOI | MR

[6] Pisinger D., “An expanding-core algorithm for the exact 0-l knapsack problem”, Eur. J. Oper. Res., 87:1 (1995), 175–187 | DOI | MR

[7] Pisinger D., “A fast algorithm for strongly correlated knapsack problems”, Discrete Applied Mathematics, 89:1–3 (1998), 197–212 | DOI | MR

[8] Dantzig G. B., “Discrete Variable Extremum Problems”, Operation Ressearch, 5 (1957), 266–277 | DOI | MR

[9] Posypkin M.A., Sigal I.Kh., “Kombinirovannyj parallelnyj algoritm reshenija zadachi o rance”, Proceedings of the Fourth International Conference “Parallel Computations and Control Problems”, M., 2008, 177–189 (in Russian)

[10] Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki, Yaroslavl, 2001 (in Russian)

[11] Vasilchikov V.V., Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem .NET Framework, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM No 2013619925, 2013 (in Russian)

[12] Vasilchikov V. V., Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya .NET Framework, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM No 2013619926, 2013 (in Russian) | MR

[13] Vasilchikov V. V., “On the Recursive-Parallel Programming for the .NET Framework”, Modeling and Analysis of Information Systems, 21:2 (2014), 15–25 (in Russian)

[14] Vasilchikov V. V., “On Optimization and Parallelization of the Little Algorithm for Solving the Travelling Salesman Problem”, Modeling and Analysis of Information Systems, 23:4 (2016), 401–411 (in Russian) | MR