Title
Unranking combinations using gradient-based optimization
Date Issued
13 December 2018
Access level
metadata only access
Resource Type
conference paper
Author(s)
Miyashita T.
Waseda University
Publisher(s)
IEEE Computer Society
Abstract
Combinations of m out of n are ubiquitous to model a wide class of combinatorial problems. For an ordered sequence of combinations, the unranking function generates the combination associated to an integer number in the ordered sequence. In this paper, we present a new method for unranking combinations by using a gradient-based optimization approach. Exhaustive experiments within computable allowable limits confirmed the feasibility and efficiency of our proposed approach. Particularly, our algorithmic realization aided by a Graphics Processing Unit (GPU) was able to generate arbitrary combinations within 0.571 seconds and 8 iterations in the worst case scenario, for n up to 1000 and m up to 100. Also, the performance and efficiency to generate combinations are independent of n, being meritorious when n is very large compared to m, or when n is time-varying. Furthermore, the number of required iterations to generate the combinations by the gradient-based optimization decreases with m in average, implying the attractive scalability in terms of m. Our proposed approach offers the building blocks to enable the succinct modeling and the efficient optimization of combinatorial structures.
Start page
579
End page
586
Volume
2018-November
Language
English
OCDE Knowledge area
Ingeniería de sistemas y comunicaciones
Matemáticas aplicadas
Subjects
Scopus EID
2-s2.0-85060821842
ISSN of the container
10823409
ISBN of the container
9781538674499
Conference
Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Sponsor(s)
We acknowledge the support from Kakenhi No. 15K18095 to fund this work. Also, we would like to thank Prof. Gautam Dasgupta for the helpful discussions and suggestions.
Sources of information:
Directorio de Producción Científica
Scopus