A Multi-Branch-and-Bound Binary Parallel Algorithm to Solve the Knapsack Problem 0–1 in a Multicore Cluster
| Autor: | Jacqueline López-Calderón, Marco Antonio Cruz-Chávez, José Alberto Hernández-Aguilar, Martha Elena Luna-Ortíz, José Crispín Zavala-Díaz |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Fluid Flow and Transfer Processes
Multi-core processor Speedup weakly correlated Branch and bound Computer science Process Chemistry and Technology General Engineering Process (computing) Parallel algorithm uncorrelated Binary number 020206 networking & telecommunications 02 engineering and technology Computer Science Applications Knapsack problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing General Materials Science Instrumentation Algorithm superlinear speedup Sequential algorithm |
| Zdroj: | Applied Sciences Volume 9 Issue 24 |
| ISSN: | 2076-3417 |
| DOI: | 10.3390/app9245368 |
| Popis: | This paper presents a process that is based on sets of parts, where elements are fixed and removed to form different binary branch-and-bound (BB) trees, which in turn are used to build a parallel algorithm called &ldquo multi-BB&rdquo These sequential and parallel algorithms calculate the exact solution for the 0&ndash 1 knapsack problem. The sequential algorithm solves the instances published by other researchers (and the proposals by Pisinger) to solve the not-so-complex (uncorrelated) class and some problems of the medium-complex (weakly correlated) class. The parallel algorithm solves the problems that cannot be solved with the sequential algorithm of the weakly correlated class in a cluster of multicore processors. The multi-branch-and-bound algorithms obtained parallel efficiencies of approximately 75%, but in some cases, it was possible to obtain a superlinear speedup. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|