TY - GEN

T1 - Generating combinations on the GPU and its application to the k-subset sum

AU - Parque, Victor

N1 - Funding Information:
This research was supported by JSPS KAKENHI 20K11998.
Publisher Copyright:
© 2021 ACM.

PY - 2021/7/7

Y1 - 2021/7/7

N2 - Efficiently representing and generating combinations can allow the seamless visualization, sampling, and evaluation of combinatorial architectures. In this paper, being relevant to tackle resource allocation problems ubiquitously, we address the subset sum problem by (1) using gradient-free optimization with a number-based representation of the combinatorial search space and by (2) generating combinations with minimal change order through 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. Since the search space of number-based representations is one-dimensional and amenable to parallelization schemes (e.g., GPU), we believe our work opens the door to tackle further combinatorial problems.

AB - Efficiently representing and generating combinations can allow the seamless visualization, sampling, and evaluation of combinatorial architectures. In this paper, being relevant to tackle resource allocation problems ubiquitously, we address the subset sum problem by (1) using gradient-free optimization with a number-based representation of the combinatorial search space and by (2) generating combinations with minimal change order through 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. Since the search space of number-based representations is one-dimensional and amenable to parallelization schemes (e.g., GPU), we believe our work opens the door to tackle further combinatorial problems.

KW - GPUs

KW - combinations

KW - differential evolution

KW - enumerative encoding

KW - gradient-free

KW - knapsack problem

KW - number representation

KW - optimization

KW - parallel reduction

KW - particle swarm

KW - subset sum

UR - http://www.scopus.com/inward/record.url?scp=85111026522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85111026522&partnerID=8YFLogxK

U2 - 10.1145/3449726.3463226

DO - 10.1145/3449726.3463226

M3 - Conference contribution

AN - SCOPUS:85111026522

T3 - GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

SP - 1308

EP - 1316

BT - GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

PB - Association for Computing Machinery, Inc

T2 - 2021 Genetic and Evolutionary Computation Conference, GECCO 2021

Y2 - 10 July 2021 through 14 July 2021

ER -