{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T02:53:45Z","timestamp":1793242425447,"version":"4.5.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T00:00:00Z","timestamp":1774828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T00:00:00Z","timestamp":1774828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005711","name":"Universit\u00e4t Hamburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This paper introduces an extended version of the min-Knapsack Problem with Compactness Constraints (mKPC), referred to as the min-Knapsack Problem with Compactness Constraints and Penalty Values (mKPCP). In this extension, penalty values are assigned to specific items that incur additional cost when excluded from the knapsack. Alongside the cost, weight, and compactness constraints of the original mKPC, which enforce proximity among selected items, the mKPCP integrates these penalties as soft constraints to reflect the importance of certain items. To solve the mKPCP, we propose a matheuristic method that combines the learning mechanism of the Fixed Set Search (FSS) metaheuristic with integer programming (IP) to improve partial solutions throughout the search process. A greedy randomized algorithm is employed to generate the initial population, promoting both diversity and solution quality. New instances are generated to evaluate the performance of the proposed method on the mKPCP. In addition, the method is tested on the mKPC and compared with existing mixed-integer programming (MIP) based techniques, such as compact MIP and branch-and-cut algorithms. Experimental results demonstrate that the proposed approach yields competitive performance across a wide range of instances. Furthermore, the method is problem-independent in nature and can be adapted to other binary optimization problems, such as the minimum vertex cover and facility location problems, with very little modifications.<\/jats:p>","DOI":"10.1007\/s10732-026-09589-2","type":"journal-article","created":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T11:52:05Z","timestamp":1774871525000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fixed set search matheuristic applied to the min-Knapsack problem with compactness constraints and an extension incorporating penalty values"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1031-659X","authenticated-orcid":false,"given":"Ahmet","family":"C\u00fcrebal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1296-4221","authenticated-orcid":false,"given":"Stefan","family":"Vo\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8167-1516","authenticated-orcid":false,"given":"Raka","family":"Jovanovic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,3,30]]},"reference":[{"issue":"2","key":"9589_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.ejor.2004.06.023","volume":"170","author":"U Akinc","year":"2006","unstructured":"Akinc, U.: Approximate and exact algorithms for the fixed-charge knapsack problem. Eur. J. Oper. Res. 170(2), 363\u2013375 (2006). https:\/\/doi.org\/10.1016\/j.ejor.2004.06.023","journal-title":"Eur. J. Oper. Res."},{"key":"9589_CR2","doi-asserted-by":"publisher","unstructured":"Boschetti, M.A., Maniezzo, V.: Matheuristics: using mathematics for heuristic design. 4OR 20(2), 173\u2013208 (2022) https:\/\/doi.org\/10.1007\/s10288-022-00510-8","DOI":"10.1007\/s10288-022-00510-8"},{"key":"9589_CR3","unstructured":"Cappello, L.: Prisca. Github repository (2022). https:\/\/www.github.com\/lorenzocapp\/ prisca Accessed 2025-03-15"},{"key":"9589_CR4","doi-asserted-by":"publisher","unstructured":"Capobianco, G., D\u2019Ambrosio, C., Pavone, L., Raiconi, A., Vitale, G., Sebastiano, F.: A hybrid metaheuristic for the knapsack problem with forfeits. Soft Computing 26, 749\u2013762 (2022) https:\/\/doi.org\/10.1007\/s00500-021-06331-x","DOI":"10.1007\/s00500-021-06331-x"},{"key":"9589_CR5","doi-asserted-by":"publisher","unstructured":"Cerulli, R., D\u2019Ambrosio, C., Raiconi, A., Vitale, G.: The knapsack problem with forfeits. In: Combinatorial Optimization: 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4\u20136, 2020, Revised Selected Papers 6, pp. 263\u2013272 (2020). https:\/\/doi.org\/10.1007\/978-3-030-53262-8_22 . Springer","DOI":"10.1007\/978-3-030-53262-8_22"},{"issue":"1\u20132","key":"9589_CR6","first-page":"15","volume":"10","author":"J Csirik","year":"1991","unstructured":"Csirik, J., Frenk, J.B.G., Labb\u00e9, M., Zhang, S.: Heuristics for the 0\u20131 min-knapsack problem. Acta Cybernet. 10(1\u20132), 15\u201320 (1991)","journal-title":"Acta Cybernet."},{"key":"9589_CR7","doi-asserted-by":"publisher","unstructured":"Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems \u2014 an overview of recent advances. Part I: single knapsack problems. Computers & Operations Research 143, 105692 (2022a) https:\/\/doi.org\/10.1016\/j.cor.2021.105692","DOI":"10.1016\/j.cor.2021.105692"},{"key":"9589_CR8","doi-asserted-by":"publisher","unstructured":"Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems \u2014 an overview of recent advances. Part II: multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research 143, 105693 (2022b) https:\/\/doi.org\/10.1016\/j.cor.2021.105693","DOI":"10.1016\/j.cor.2021.105693"},{"issue":"4","key":"9589_CR9","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.orl.2005.06.001","volume":"34","author":"A Ceselli","year":"2006","unstructured":"Ceselli, A., Righini, G.: An optimization algorithm for a penalized knapsack problem. Oper. Res. Lett. 34(4), 394\u2013404 (2006). https:\/\/doi.org\/10.1016\/j.orl.2005.06.001","journal-title":"Oper. Res. Lett."},{"key":"9589_CR10","doi-asserted-by":"publisher","unstructured":"C\u00fcrebal, A., Vo\u00df, S., Jovanovic, R.: Fixed set search matheuristic applied to the min-knapsack problem with compactness constraints and penalty values. In: Sevaux, M., Olteanu, A.-L., Pardo, E.G., Sifaleras, A., Makboul, S. (eds.) Metaheuristics, pp. 264\u2013278. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-62922-8_18","DOI":"10.1007\/978-3-031-62922-8_18"},{"key":"9589_CR11","doi-asserted-by":"crossref","unstructured":"C\u00fcrebal, A.: Matheuristic fixed set search for the min-knapsack problem with compactness constraints and penalty values. Github repository (2024). https:\/\/github.com\/ahmet-cuerebal\/MFSS_mKPCP Accessed 2025-03-31","DOI":"10.1007\/978-3-031-62922-8_18"},{"key":"9589_CR12","doi-asserted-by":"publisher","unstructured":"Della\u00a0Croce, F., Pferschy, U., Scatamacchia, R.: New exact approaches and approximation results for the penalized knapsack problem. Discrete Applied Mathematics 253, 122\u2013135 (2019) https:\/\/doi.org\/10.1016\/j.dam.2017.11.023","DOI":"10.1016\/j.dam.2017.11.023"},{"key":"9589_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.106093","volume":"151","author":"C D\u2019Ambrosio","year":"2023","unstructured":"D\u2019Ambrosio, C., Laureana, F., Raiconi, A., Vitale, G.: The knapsack problem with forfeit sets. Computers & Operations Research 151, 106093 (2023). https:\/\/doi.org\/10.1016\/j.cor.2022.106093","journal-title":"Computers & Operations Research"},{"key":"9589_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6, 109\u2013133 (1995). https:\/\/doi.org\/10.1007\/BF01096763","journal-title":"J. Global Optim."},{"issue":"3","key":"9589_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6377(87)90021-6","volume":"6","author":"JP Hart","year":"1987","unstructured":"Hart, J.P., Shogan, A.W.: Semi-greedy heuristics: An empirical study. Oper. Res. Lett. 6(3), 107\u2013114 (1987). https:\/\/doi.org\/10.1016\/0167-6377(87)90021-6","journal-title":"Oper. Res. Lett."},{"key":"9589_CR16","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Bayhan, S., Vo\u00df, S.: Matheuristic fixed set search applied to electric bus fleet scheduling. In: International Conference on Learning and Intelligent Optimization, pp. 393\u2013407 (2023a). https:\/\/doi.org\/10.1007\/978-3-031-44505-7_27. Springer","DOI":"10.1007\/978-3-031-44505-7_27"},{"key":"9589_CR17","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Sanfilippo, A., Vo\u00df, S.: Fixed set search applied to the clique partitioning problem. Eur. J. Oper. Res. 309, 65\u201381 (2023b). https:\/\/doi.org\/10.1016\/j.ejor.2023.01.044","DOI":"10.1016\/j.ejor.2023.01.044"},{"key":"9589_CR18","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Tuba, M., Vo\u00df, S.: Fixed set search applied to the traveling salesman problem. In: Hybrid Metaheuristics: 11th International Workshop, HM 2019, Concepci\u00f3n, Chile, pp. 63\u201377 (2019). https:\/\/doi.org\/10.1007\/978-3-030-05983-5_5 . Springer","DOI":"10.1007\/978-3-030-05983-5_5"},{"key":"9589_CR19","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search applied to the minimum weighted vertex cover problem. In: Analysis of Experimental Algorithms: Special Event, SEA$$^2$$ 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers, pp. 490\u2013504 (2019). https:\/\/doi.org\/10.1007\/978-3-030-34029-2_31 . Springer","DOI":"10.1007\/978-3-030-34029-2_31"},{"issue":"6","key":"9589_CR20","doi-asserted-by":"publisher","first-page":"12559","DOI":"10.1111\/exsy.12559","volume":"37","author":"R Jovanovic","year":"2020","unstructured":"Jovanovic, R., Vo\u00df, S.: The fixed set search applied to the power dominating set problem. Expert. Syst. 37(6), 12559 (2020). https:\/\/doi.org\/10.1111\/exsy.12559","journal-title":"Expert. Syst."},{"key":"9589_CR21","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times. Applied Soft Computing 110, 107521 (2021) https:\/\/doi.org\/10.1016\/j.asoc.2021.107521","DOI":"10.1016\/j.asoc.2021.107521"},{"key":"9589_CR22","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets. OR Spectrum 46(4), 1329\u20131365 (2024a). https:\/\/doi.org\/10.1007\/s00291-024-00746-2","DOI":"10.1007\/s00291-024-00746-2"},{"key":"9589_CR23","doi-asserted-by":"publisher","unstructured":"Jovanovic, R., Vo\u00df, S.: Fixed set search matheuristic applied to the knapsack problem with forfeits. Computers & Operations Research 168, 106685 (2024b) https:\/\/doi.org\/10.1016\/j.cor.2024.106685","DOI":"10.1016\/j.cor.2024.106685"},{"key":"9589_CR24","doi-asserted-by":"publisher","unstructured":"Lozano-Osorio, I., S\u00e1nchez-Oro, J., Mart\u00ednez-Gavara, A., L\u00f3pez-S\u00e1nchez, A.D., Duarte, A.: An efficient fixed set search for the covering location with interconnected facilities problem. In: Metaheuristics International Conference, pp. 485\u2013490 (2022). https:\/\/doi.org\/10.1007\/978-3-031-26504-4_37 . Springer","DOI":"10.1007\/978-3-031-26504-4_37"},{"key":"9589_CR25","doi-asserted-by":"publisher","unstructured":"Monaci, M., Pike-Burke, C., Santini, A.: Exact algorithms for the 0\u20131 time-bomb knapsack problem. Computers & Operations Research 145, 105848 (2022) https:\/\/doi.org\/10.1016\/j.cor.2022.105848","DOI":"10.1016\/j.cor.2022.105848"},{"key":"9589_CR26","doi-asserted-by":"publisher","unstructured":"Madhukar, E., Ragunathan, T.: Improved GRASP technique based resource allocation in the cloud. International Journal of Advanced Computer Science and Applications 12(11) (2021) https:\/\/doi.org\/10.14569\/IJACSA.2021.0121155","DOI":"10.14569\/IJACSA.2021.0121155"},{"key":"9589_CR27","doi-asserted-by":"publisher","unstructured":"Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures: Advances and extensions. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, pp. 169\u2013220. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-319-91086-4_6","DOI":"10.1007\/978-3-319-91086-4_6"},{"key":"9589_CR28","doi-asserted-by":"publisher","unstructured":"Santini, A.: Algorithms for the min-Knapsack problem with compactness constraints. Github repository (2022). https:\/\/doi.org\/10.5281\/zenodo.7492799. https:\/\/github.com\/alberto-santini\/min-knapsack-with-compactness Accessed 2025-03-15","DOI":"10.5281\/zenodo.7492799"},{"issue":"1","key":"9589_CR29","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/j.ejor.2023.07.020","volume":"312","author":"A Santini","year":"2024","unstructured":"Santini, A., Malaguti, E.: The min-knapsack problem with compactness constraints and applications in statistics. Eur. J. Oper. Res. 312(1), 385\u2013397 (2024). https:\/\/doi.org\/10.1016\/j.ejor.2023.07.020","journal-title":"Eur. J. Oper. Res."},{"key":"9589_CR30","doi-asserted-by":"publisher","unstructured":"Sondergeld, L., Vo\u00df, S.: Cooperative intelligent search using adaptive memory techniques. In: Vo\u00df, S., Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 297\u2013312. Kluwer, Boston, MA (1999). https:\/\/doi.org\/10.1007\/978-1-4615-5775-3_21","DOI":"10.1007\/978-1-4615-5775-3_21"},{"issue":"3","key":"9589_CR31","first-page":"551","volume":"35","author":"M Sniedovich","year":"2006","unstructured":"Sniedovich, M., Vo\u00df, S.: The corridor method: A dynamic programming inspired metaheuristic. Cybernetics 35(3), 551\u2013578 (2006)","journal-title":"Cybernetics"},{"key":"9589_CR32","doi-asserted-by":"publisher","unstructured":"Taillard, E.D., Vo\u00df, S.: POPMUSIC \u2013 partial optimization metaheuristic under special intensification conditions. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 613\u2013629. Kluwer, Boston, MA (2002). https:\/\/doi.org\/10.1007\/978-1-4615-1507-4_27","DOI":"10.1007\/978-1-4615-1507-4_27"},{"key":"9589_CR33","unstructured":"Van den Burg, G.J.J., Williams, C.K.I.: An evaluation of change point detection algorithms. arXiv preprint arXiv:2003.06222 (2020)"},{"key":"9589_CR34","first-page":"335","volume":"40","author":"S Vo\u00df","year":"1997","unstructured":"Vo\u00df, S., Gutenschwager, K.: A chunking based genetic algorithm for the Steiner tree problem in graphs. Network Design: Connectivity and Facilities Location 40, 335\u2013355 (1997)","journal-title":"Network Design: Connectivity and Facilities Location"},{"issue":"2\u20133","key":"9589_CR35","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/S0377-2217(97)00293-2","volume":"106","author":"DL Woodruff","year":"1998","unstructured":"Woodruff, D.L.: Proposals for chunking and tabu search. Eur. J. Oper. Res. 106(2\u20133), 585\u2013598 (1998). https:\/\/doi.org\/10.1016\/S0377-2217(97)00293-2","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"9589_CR36","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1016\/j.ejor.2007.10.024","volume":"192","author":"T Yamada","year":"2009","unstructured":"Yamada, T., Takeoka, T.: An exact algorithm for the fixed-charge multiple knapsack problem. Eur. J. Oper. Res. 192(2), 700\u2013705 (2009). https:\/\/doi.org\/10.1016\/j.ejor.2007.10.024","journal-title":"Eur. J. Oper. Res."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09589-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-026-09589-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-026-09589-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T02:19:37Z","timestamp":1780625977000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-026-09589-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,30]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["9589"],"URL":"https:\/\/doi.org\/10.1007\/s10732-026-09589-2","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,30]]},"assertion":[{"value":"3 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest regarding the publication of this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials availability"}}],"article-number":"16"}}