On k-subset sum using enumerative encoding

Victor Parque Tenorio; Tomoyuki Miyashita

doi:10.1109/ISSPIT.2016.7886013

On k-subset sum using enumerative encoding

Victor Parque Tenorio, Tomoyuki Miyashita

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Citations (Scopus)

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 10¹⁴ integer numbers, we show that our approach is effective and efficient: it is feasible to find any combination with a user-defined sum within 10⁴ 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.

Original language	English
Title of host publication	2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	81-86
Number of pages	6
ISBN (Electronic)	9781509058440
DOIs	https://doi.org/10.1109/ISSPIT.2016.7886013
Publication status	Published - 2017 Mar 23
Event	2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016 - Limassol, Cyprus Duration: 2016 Dec 12 → 2016 Dec 14

Other

Other	2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016
Country/Territory	Cyprus
City	Limassol
Period	16/12/12 → 16/12/14

ASJC Scopus subject areas

Computer Networks and Communications
Computer Science Applications
Signal Processing

Access to Document

10.1109/ISSPIT.2016.7886013

Cite this

Parque Tenorio, V & Miyashita, T 2017, On k-subset sum using enumerative encoding. in 2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016., 7886013, Institute of Electrical and Electronics Engineers Inc., pp. 81-86, 2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016, Limassol, Cyprus, 16/12/12. https://doi.org/10.1109/ISSPIT.2016.7886013

@inproceedings{e3ce6e89673547ba8db0d801a21b90bb,

title = "On k-subset sum using enumerative encoding",

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.",

author = "{Parque Tenorio}, Victor and Tomoyuki Miyashita",

year = "2017",

month = mar,

day = "23",

doi = "10.1109/ISSPIT.2016.7886013",

language = "English",

pages = "81--86",

booktitle = "2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

}

TY - GEN

T1 - On k-subset sum using enumerative encoding

AU - Parque Tenorio, Victor

AU - Miyashita, Tomoyuki

PY - 2017/3/23

Y1 - 2017/3/23

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/ISSPIT.2016.7886013

DO - 10.1109/ISSPIT.2016.7886013

M3 - Conference contribution

AN - SCOPUS:85017608290

SP - 81

EP - 86

BT - 2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Signal Processing and Information Technology, ISSPIT 2016

Y2 - 12 December 2016 through 14 December 2016

ER -

On k-subset sum using enumerative encoding

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this