What is it about?
We address the subset sum problem by gradient-free optimization algorithms searching over numbers generated by parallel reductions in the GPU. Our computational experiments consisting of a relevant set of problem instances and gradient-free optimization algorithms show that (1) it is possible to generate combinations in the GPU efficiently, with quasi-linear complexity, (2) it is possible to tackle instances of the subset sum problem within a reasonable number of function evaluations, and (3) Particle Swarm Optimization with Fitness Euclidean Ratio converges faster.
Featured Image
Photo by Susan Holt Simpson on Unsplash
Why is it important?
Generating combinations efficiently enables the seamless visualization, sampling, and evaluation of solutions to combinatorial problems.
Perspectives
Our approach enables us to model a one-dimensional search space that is amenable to further parallelization schemes (e.g., multi GPU and multi-core CPUs). We believe our work facilitates tackling combinatorial problems by using enumerative encodings.
Victor Parque
Read the Original
This page is a summary of: Generating combinations on the GPU and its application to the k-subset sum, July 2021, ACM (Association for Computing Machinery),
DOI: 10.1145/3449726.3463226.
You can read the full text:
Resources
Contributors
The following have contributed to this page
