EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

Clustering-Guided Automatic Generation of Algorithms for the Multidimensional Knapsack Problem

Cristian Inzulza, Caio Bezares, Franco Cornejo, Victor Parada

Machine Learning and Knowledge Extraction · 2025-11-12 · 7 (4) · 144

DOI: 10.3390/make7040144 ↗

At a glance

Journal article in Machine Learning and Knowledge Extraction, published online on 2025-11-12. Written by Cristian Inzulza and 3 co-authors. Cited 3 times so far (Crossref); 60 references. The full text is freely available (open access, CC BY 4.0). Funded by: Agencia Nacional de Investigación y Desarrollo, University of Santiago of Chile.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

We propose a hybrid framework that integrates instance clustering with Automatic Generation of Algorithms (AGA) to produce specialized algorithms for classes of Multidimensional Knapsack Problem (MKP) instances. This approach is highly relevant given the latest trends in AI, where Large Language Models (LLMs) are actively being used to automate and refine algorithm design through evolutionary frameworks. Our method utilizes a feature-based representation of 328 MKP instances and evaluates K-means, HDBSCAN, and random clustering to produce 11 clusters per method. For each cluster, a master optimization problem was solved using Genetic Programming, evolving algorithms encoded as syntax trees. Fitness was measured as relative error against known optima, a similar objective to those being tackled in LLM-driven optimization. Experimental and statistical analyses demonstrate that clustering-guided AGA significantly reduces average relative error and accelerates convergence compared with AGA trained on randomly grouped instances. K-means produced the most consistent cluster-specialization. Cross-cluster evaluation reveals a trade-off between specialization and generalization. The results demonstrate that clustering prior to AGA is a practical preprocessing step for designing automated algorithms in NP-hard combinatorial problems, paving the way for advanced methodologies that incorporate AI techniques.

Funding

  • Agencia Nacional de Investigación y Desarrollo
  • University of Santiago of Chile

Cite

APA

Inzulza, C., Bezares, C., Cornejo, F., & Parada, V. (2025). Clustering-Guided Automatic Generation of Algorithms for the Multidimensional Knapsack Problem. Machine Learning and Knowledge Extraction, 7(4), 144. https://doi.org/10.3390/make7040144

Vancouver

Inzulza C, Bezares C, Cornejo F, Parada V. Clustering-Guided Automatic Generation of Algorithms for the Multidimensional Knapsack Problem. Machine Learning and Knowledge Extraction. 2025;7(4):144. doi:10.3390/make7040144

BibTeX
@article{Inzulza2025,
  author = {Inzulza, Cristian and Bezares, Caio and Cornejo, Franco and Parada, Victor},
  title = {Clustering-Guided Automatic Generation of Algorithms for the Multidimensional Knapsack Problem},
  journal = {Machine Learning and Knowledge Extraction},
  year = {2025},
  volume = {7},
  number = {4},
  pages = {144},
  doi = {10.3390/make7040144}
}
Start for free →