KP01 Solved by an n-Dimensional Sampling and Clustering Heuristic
Harita, Maria (Universitat Autònoma de Barcelona)
Wong, Álvaro (Universitat Autònoma de Barcelona)
Rexachs del Rosario, Dolores Isabel (Universitat Autònoma de Barcelona)
Luque, Emilio (Universitat Autònoma de Barcelona)

Imprint:	Cham, Switzerland: Springer, 2022
Abstract:	In the field of optimization, NP-Hard problems play an important role concerning its real-world applications, such as resource allocation, scheduling, planning, logistics, etc. In this paper, we propose a heuristic search algorithm based on Montecarlo along with a clustering strategy that analyzes density and performs k-means partitions to solve the classic binary Knapsack Problem (KP01). Our heuristic method, which was designed to solve combinatorial optimization problems, has evolved and can adapt to other optimization problems, such as the KP01 that can be organized in an n-Dimensional search space. Regarding the methodology, we substantially reduced the search space while the areas of interest were located in the clustering stage, which brings us closer to the best solutions. After the experiments, we obtained a high-quality solution, which resulted in an average success rate of above 90%.
Grants:	Agencia Estatal de Investigación PID2020-112496GB-I00
Rights:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Language:	Anglès
Series:	Lecture Notes in Computer Science ; 13351
Document:	Capítol de llibre ; recerca ; Versió acceptada per publicar
Subject:	01 Knapsack Problem ; Clustering ; Heuristic method
Published in:	Computational Science - ICCS 2022, 2022, p. 229-236, ISBN 978-3-031-08754-7

DOI: 10.1007/978-3-031-08754-7_31

Postprint 8 p, 1.2 MB

The record appears in these collections:
Books and collections > Book chapters