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 -