{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T03:25:27Z","timestamp":1771039527900,"version":"3.50.1"},"reference-count":60,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:00:00Z","timestamp":1762905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"crossref","award":["PIA\/PUENTE AFB230002"],"award-info":[{"award-number":["PIA\/PUENTE AFB230002"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"crossref","award":["21201924"],"award-info":[{"award-number":["21201924"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"name":"University of Santiago of Chile","award":["VP2022-VRID-USACH"],"award-info":[{"award-number":["VP2022-VRID-USACH"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["MAKE"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/make7040144","type":"journal-article","created":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T09:10:45Z","timestamp":1763025045000},"page":"144","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Clustering-Guided Automatic Generation of Algorithms for the Multidimensional Knapsack Problem"],"prefix":"10.3390","volume":"7","author":[{"given":"Cristian","family":"Inzulza","sequence":"first","affiliation":[{"name":"Departamento de Ingenier\u00eda Inform\u00e1tica, Universidad de Santiago de Chile, Santiago 9170124, Chile"},{"name":"Faculty of Engineering and Architecture, Universidad Central de Chile, Santiago 8330601, Chile"}]},{"given":"Caio","family":"Bezares","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Inform\u00e1tica, Universidad de Santiago de Chile, Santiago 9170124, Chile"}]},{"given":"Franco","family":"Cornejo","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Inform\u00e1tica, Universidad de Santiago de Chile, Santiago 9170124, Chile"}]},{"given":"Victor","family":"Parada","sequence":"additional","affiliation":[{"name":"Departamento de Ingenier\u00eda Inform\u00e1tica, Universidad de Santiago de Chile, Santiago 9170124, Chile"}]}],"member":"1968","published-online":{"date-parts":[[2025,11,12]]},"reference":[{"key":"ref_1","unstructured":"Martello, S., and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(03)00274-1","article-title":"The multidimensional 0\u20131 knapsack problem: An overview","volume":"155","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"105693","DOI":"10.1016\/j.cor.2021.105693","article-title":"Knapsack problems\u2014An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems","volume":"143","author":"Cacchiani","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Song, Y., Zhang, C., and Fang, Y. (2008, January 16\u201319). Multiple multidimensional knapsack problem and its applications in cognitive radio networks. Proceedings of the MILCOM 2008\u20142008 IEEE Military Communications Conference, San Diego, CA, USA.","DOI":"10.1109\/MILCOM.2008.4753629"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1500","DOI":"10.1108\/K-09-2013-0201","article-title":"A genetic programming hyper-heuristic for the multidimensional knapsack problem","volume":"43","author":"Drake","year":"2014","journal-title":"Kybernetes"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1951","DOI":"10.1007\/s13042-020-01085-8","article-title":"Enhancing a machine learning binarization framework by perturbation operators: Analysis on the multidimensional knapsack problem","volume":"11","author":"Droguett","year":"2020","journal-title":"Int. J. Mach. Learn. Cybern."},{"key":"ref_7","first-page":"395","article-title":"The 0\/1 multidimensional knapsack problem and its variants: A survey of practical models and heuristic approaches","volume":"08","author":"Laabadi","year":"2018","journal-title":"Am. J. Oper. Res."},{"key":"ref_8","first-page":"1061","article-title":"A core-based exact algorithm for the multidimensional multiple choice knapsack problem","volume":"32","author":"Mansini","year":"2020","journal-title":"Inf. J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s10878-006-9035-3","article-title":"A best first search exact algorithm for the multiple-choice multidimensional knapsack problem","volume":"13","author":"Sbihi","year":"2007","journal-title":"J. Comb. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.ejor.2019.09.016","article-title":"Empirical orthogonal constraint generation for multidimensional 0\/1 knapsack problems","volume":"282","author":"Setzer","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s10479-006-0150-4","article-title":"Greedy algorithm for the general multidimensional knapsack problem","volume":"150","author":"Akcay","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0377-2217(84)90286-8","article-title":"A heuristic algorithm for the multidimensional zero-one knapsack problem","volume":"16","author":"Magazine","year":"1984","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s11590-020-01611-1","article-title":"A randomized heuristic repair for the multidimensional knapsack problem","volume":"15","author":"Martins","year":"2021","journal-title":"Optim. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"B-196","DOI":"10.1287\/mnsc.15.4.B196","article-title":"An approach to linear programming with 0\u20131 variables","volume":"15","author":"Senju","year":"1968","journal-title":"Manag. Sci."},{"key":"ref_15","first-page":"963","article-title":"An improved heuristic for multidimensional 0-1 knapsack problems","volume":"41","author":"Volgenant","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"ref_16","first-page":"2272672","article-title":"An improved adaptive human learning optimization algorithm with reasoning learning","volume":"2022","author":"Zhang","year":"2022","journal-title":"Sci. Program."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1009642405419","article-title":"A genetic algorithm for the multidimensional knapsack problem","volume":"4","author":"Chu","year":"1998","journal-title":"J. Heuristics"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1162\/EVCO_a_00145","article-title":"A case study of controlling crossover in a selection hyper-heuristic framework using the multidimensional knapsack problem","volume":"24","author":"Drake","year":"2016","journal-title":"Evol. Comput."},{"key":"ref_19","first-page":"2260","article-title":"An improved sexual genetic algorithm for solving 0\/1 multidimensional knapsack problem","volume":"36","author":"Laabadi","year":"2019","journal-title":"Eng. Comput."},{"key":"ref_20","first-page":"404","article-title":"An evolutionary computation based on immune operation for constraint optimization problems","volume":"39","author":"Zhang","year":"2016","journal-title":"Rev. Tec. Fac. Ing. Univ. Zulia"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"112908","DOI":"10.1016\/j.eswa.2019.112908","article-title":"Automatic design of specialized algorithms for the binary knapsack problem","volume":"141","author":"Acevedo","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ryser-Welch, P., Miller, J.F., and Asta, S. (2015, January 11\u201315). Generating human-readable algorithms for the travelling salesman problem using hyper-heuristics. Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain.","DOI":"10.1145\/2739482.2768459"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"110474","DOI":"10.1016\/j.asoc.2023.110474","article-title":"Automatic generation of a hybrid algorithm for the maximum independent set problem using genetic programming","volume":"144","author":"Rey","year":"2023","journal-title":"Appl. Soft Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s10100-018-0569-0","article-title":"Complexity indices for the multidimensional knapsack problem","volume":"29","author":"Derpich","year":"2021","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_25","unstructured":"Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1109\/TEVC.2024.3497793","article-title":"LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics","volume":"29","year":"2025","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"105364","DOI":"10.1016\/j.cor.2021.105364","article-title":"Automatic generation of algorithms for robust optimisation problems using Grammar-Guided Genetic Programming","volume":"133","author":"Hughes","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_28","unstructured":"Liu, F., Tong, X., Yuan, M., and Zhang, Q. (2023). Algorithm Evolution Using Large Language Model. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"103151","DOI":"10.1016\/j.artmed.2025.103151","article-title":"Surgery scheduling based on large language models","volume":"166","author":"Wan","year":"2025","journal-title":"Artif. Intell. Med."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Xie, Z., Liu, F., Li, G., Mao, Z., Zhang, Y., Wang, Z., and Zhang, Q. (2025). Multipopulation Optimization With LLM-Driven Knowledge Discovery for Large-Scale HFVRP. IEEE Trans. Comput. Soc. Syst., 1\u201311.","DOI":"10.1109\/TCSS.2025.3571479"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2329","DOI":"10.1093\/ietisy\/e88-d.10.2329","article-title":"Enumeration methods for repeatedly solving multidimensional knapsack sub-problems","volume":"E88D","author":"James","year":"2005","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1287\/ijoc.1110.0460","article-title":"CORAL: An exact algorithm for the multidimensional knapsack problem","volume":"24","author":"Mansini","year":"2012","journal-title":"Inf. J. Comput."},{"key":"ref_33","first-page":"97","article-title":"A multi-level search strategy for the 0\u20131 multidimensional knapsack problem. Discrete Appl","volume":"158","author":"Boussier","year":"2010","journal-title":"Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1016\/j.orl.2022.10.003","article-title":"Revisiting surrogate relaxation for the multidimensional knapsack problem","volume":"50","author":"Dokka","year":"2022","journal-title":"Oper. Res. Lett."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2247","DOI":"10.1111\/itor.13207","article-title":"A decomposition approach for multidimensional knapsacks with family-split penalties","volume":"31","author":"Mancini","year":"2022","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Shahbandegan, S., and Naderi, M. (2021, January 18\u201320). Multiswarm binary butterfly optimization algorithm for solving the multidimensional knapsack problem. Proceedings of the 2021 29th Iranian Conference on Electrical Engineering (ICEE), Tehran, Iran.","DOI":"10.1109\/ICEE52715.2021.9544302"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"113310","DOI":"10.1016\/j.eswa.2020.113310","article-title":"Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem","volume":"149","author":"Lai","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Fidanova, S. (2020, January 1\u20133). Hybrid Ant Colony Optimization Algorithm for Multiple Knapsack Problem. Proceedings of the 2020 5th IEEE International Conference on Recent Advances and Innovations in Engineering (ICRAIE), Jaipur, India.","DOI":"10.1109\/ICRAIE51050.2020.9358351"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1602","DOI":"10.1016\/j.cor.2008.03.003","article-title":"Fast, effective heuristics for the 0\u20131 multidimensional knapsack problem","volume":"36","author":"Fleszar","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"109682","DOI":"10.1016\/j.asoc.2022.109682","article-title":"Diversified sine\u2013cosine algorithm based on differential evolution for multidimensional knapsack problem","volume":"130","author":"Gupta","year":"2022","journal-title":"Appl. Soft Comput."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Osman, I.H., and Kelly, J.P. (1996). Critical event tabu search for multidimensional knapsack problems. Meta-Heuristics, Springer.","DOI":"10.1007\/978-1-4613-1361-8"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.1007\/s00291-024-00746-2","article-title":"Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets","volume":"46","author":"Jovanovic","year":"2024","journal-title":"OR Spectr."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.ins.2018.01.026","article-title":"A two-phase tabu-evolutionary algorithm for the 0\u20131 multidimensional knapsack problem","volume":"436\u2013437","author":"Lai","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Ferjani, A.A., and Liouane, N. (2017, January 19\u201321). Logic gate-based evolutionary algorithm for the multidimensional knapsack problem. Proceedings of the 2017 International Conference on Control, Automation and Diagnosis (ICCAD), Hammamet, Tunisia.","DOI":"10.1109\/CADIAG.2017.8075650"},{"key":"ref_45","unstructured":"Bayro-Corrochano, E., and Hancock, E. (2014). A multidimensional multiple-choice knapsack model for resource allocation in a construction equipment manufacturer setting using an evolutionary algorithm. Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Springer International Publishing."},{"key":"ref_46","unstructured":"Pardo, A., and Kittler, J. (2015). A shuffled complex evolution algorithm for the multidimensional knapsack problem. Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Springer International Publishing."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Silva-Munoz, M., Contreras-Bolton, C., Semaan, G.S., Villanueva, M., and Parada, V. (2019, January 4\u20139). Novel algorithms automatically generated for optimization problems. Proceedings of the 2019 38th International Conference of the Chilean Computer Science Society (SCCC), Concepcion, Chile.","DOI":"10.1109\/SCCC49216.2019.8966437"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0004-3702(03)00015-8","article-title":"BOB: Improved winner determination in combinatorial auctions and generalizations","volume":"145","author":"Sandholm","year":"2003","journal-title":"Artif. Intell."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1002\/nav.3800320408","article-title":"A heuristic with tie breaking for certain 0\u20131 integer programming models","volume":"32","author":"Fox","year":"1985","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Pfeiffer, J., and Rothlauf, F. (2007, January 7\u201311). Analysis of greedy heuristics and weight-coded eas for multidimensional knapsack problems and multi-unit combinatorial auctions. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, UK.","DOI":"10.1145\/1276958.1277258"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","article-title":"discrete-variable extremum problems","volume":"5","author":"Dantzig","year":"1957","journal-title":"Oper. Res."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Cotta, C., and Troya, J.M. (1998). A hybrid genetic algorithm for the 0\u20131 multiple knapsack problem. Artificial Neural Nets and Genetic Algorithms, Springer.","DOI":"10.1007\/978-3-7091-6492-1_55"},{"key":"ref_53","first-page":"147","article-title":"The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool","volume":"2","author":"Plateau","year":"1996","journal-title":"J. Heuristics"},{"key":"ref_54","unstructured":"Poli, R., Langdon, W.B., McPhee, N.F., and Koza, J.R. (2008). A field Guide to Genetic Programming, Lulu Press."},{"key":"ref_55","unstructured":"Beasley, J.E. (2025, July 19). OR-Library: Multidimensional Knapsack Problem Instances. Brunel University. Available online: https:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/orlib\/mknapinfo.html."},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Luke, S. (2017, January 15\u201319). ECJ then and now. Proceedings of the Genetic and Evolutionary Computation Conference Companion, Berlin, Germany.","DOI":"10.1145\/3067695.3082467"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10710-010-9112-3","article-title":"Human-competitive results produced by genetic programming","volume":"11","author":"Koza","year":"2010","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1007\/s00500-008-0354-4","article-title":"A case study of memetic algorithms for constraint optimization","volume":"13","year":"2009","journal-title":"Soft Comput."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A","article-title":"A heuristic solution procedure for the multiconstraint zero-one knapsack problem","volume":"34","author":"Pirkul","year":"1987","journal-title":"Nav. Res. Logist. NRL"},{"key":"ref_60","first-page":"320","article-title":"Simulated annealing for the 0\/1 multidimensional knapsack problem","volume":"16","author":"Qian","year":"2007","journal-title":"Numer. Math. J. Chin. Univ. Engl. Ser."}],"container-title":["Machine Learning and Knowledge Extraction"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2504-4990\/7\/4\/144\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T05:31:47Z","timestamp":1763098307000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2504-4990\/7\/4\/144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,12]]},"references-count":60,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["make7040144"],"URL":"https:\/\/doi.org\/10.3390\/make7040144","relation":{},"ISSN":["2504-4990"],"issn-type":[{"value":"2504-4990","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,12]]}}}