On а Recursive-Parallel Algorithm for Solving the Knapsack Problem
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 e...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2018-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/676 |
| _version_ | 1797877991943962624 |
|---|---|
| author | Vladimir V. Vasilchikov |
| author_facet | Vladimir V. Vasilchikov |
| author_sort | Vladimir V. Vasilchikov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T02:25:39Z |
| format | Article |
| id | doaj.art-117a881ec3aa4bbe8210ecd5efdb2c2f |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:25:39Z |
| publishDate | 2018-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-117a881ec3aa4bbe8210ecd5efdb2c2f2023-03-13T08:07:29ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172018-04-0125215516410.18255/1818-1015-2018-2-155-164496On а Recursive-Parallel Algorithm for Solving the Knapsack ProblemVladimir V. Vasilchikov0Ярославский государственный университет им. П.Г. Демидова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.https://www.mais-journal.ru/jour/article/view/676задача о рюкзакепараллельный алгоритмрекурсия.net |
| spellingShingle | Vladimir V. Vasilchikov On а Recursive-Parallel Algorithm for Solving the Knapsack Problem Моделирование и анализ информационных систем задача о рюкзаке параллельный алгоритм рекурсия .net |
| title | On а Recursive-Parallel Algorithm for Solving the Knapsack Problem |
| title_full | On а Recursive-Parallel Algorithm for Solving the Knapsack Problem |
| title_fullStr | On а Recursive-Parallel Algorithm for Solving the Knapsack Problem |
| title_full_unstemmed | On а Recursive-Parallel Algorithm for Solving the Knapsack Problem |
| title_short | On а Recursive-Parallel Algorithm for Solving the Knapsack Problem |
| title_sort | on а recursive parallel algorithm for solving the knapsack problem |
| topic | задача о рюкзаке параллельный алгоритм рекурсия .net |
| url | https://www.mais-journal.ru/jour/article/view/676 |
| work_keys_str_mv | AT vladimirvvasilchikov onarecursiveparallelalgorithmforsolvingtheknapsackproblem |