Title
On k-subset sum using enumerative encoding
Date Issued
23 March 2017
Access level
metadata only access
Resource Type
conference paper
Author(s)
Waseda University
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Being a significant construct in a wide range of combinatorial problems, the k-subset sum problem (k-SSP) computes k-element subsets, out of an n-element set, satisfying a user-defined aggregation value. In this paper, we formulate the k-subset sum problem as a search (optimization) problem over the space of integers associated with combination elements. And by using rigorous computational experiments using the search space over more than 1014 integer numbers, we show that our approach is effective and efficient: it is feasible to find any combination with a user-defined sum within 104 function evaluations by using a gradient-free optimization algorithm. Our scheme opens the door to further advance the understanding of combinatorial problems by improved/tailored gradient-free optimization algorithms based on enumerative encoding. Also, our approach realizes the practical building block for combinatorial problems in planning and operations research using k-SSP concepts.
Start page
81
End page
86
Language
English
OCDE Knowledge area
Ingeniería de sistemas y comunicaciones Matemáticas aplicadas
Scopus EID
2-s2.0-85017608290
ISBN of the container
9781509058440
Conference
2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016
Sources of information: Directorio de Producción Científica Scopus