{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T15:04:47Z","timestamp":1773414287538,"version":"3.50.1"},"reference-count":37,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T00:00:00Z","timestamp":1687996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper we exploit concepts from Information Theory to improve the classical Chvatal greedy algorithm for the set covering problem. In particular, we develop a new greedy procedure, called Surprisal-Based Greedy Heuristic (SBH), incorporating the computation of a \u201csurprisal\u201d measure when selecting the solution columns. Computational experiments, performed on instances from the OR-Library, showed that SBH yields a 2.5% improvement in terms of the objective function value over the Chvatal\u2019s algorithm while retaining similar execution times, making it suitable for real-time applications. The new heuristic was also compared with Kordalewski\u2019s greedy algorithm, obtaining similar solutions in much shorter times on large instances, and Grossmann and Wool\u2019s algorithm for unicost instances, where SBH obtained better solutions.<\/jats:p>","DOI":"10.3390\/a16070321","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T01:02:41Z","timestamp":1688086961000},"page":"321","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Surprisal-Based Greedy Heuristic for the Set Covering Problem"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9505-5869","authenticated-orcid":false,"given":"Tommaso","family":"Adamo","sequence":"first","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, Via per Monteroni, 73100 Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5243-1799","authenticated-orcid":false,"given":"Gianpaolo","family":"Ghiani","sequence":"additional","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, Via per Monteroni, 73100 Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8959-5017","authenticated-orcid":false,"given":"Emanuela","family":"Guerriero","sequence":"additional","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, Via per Monteroni, 73100 Lecce, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8415-4258","authenticated-orcid":false,"given":"Deborah","family":"Pareo","sequence":"additional","affiliation":[{"name":"Department of Engineering for Innovation, University of Salento, Via per Monteroni, 73100 Lecce, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1287\/trsc.7.1.34","article-title":"A technique for the solution of massive set covering problems, with application to airline crew scheduling","volume":"7","author":"Rubin","year":"1973","journal-title":"Transp. Sci."},{"key":"ref_2","unstructured":"Marchiori, E., and Steenbeek, A. (2000, January 17). An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling. Proceedings of the Real-World Applications of Evolutionary Computing: EvoWorkshops 2000: EvoIASP, EvoSCONDI, EvoTel, EvoSTIM, EvoRob, and EvoFlight Edinburgh, Scotland, UK."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02614314","article-title":"Algorithms for railway crew management","volume":"79","author":"Caprara","year":"1997","journal-title":"Math. Program."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s10479-007-0179-z","article-title":"Combinatorial auctions","volume":"153","author":"Abrache","year":"2007","journal-title":"Ann. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1057\/jors.1976.63","article-title":"An integer programming approach to the vehicle scheduling problem","volume":"27","author":"Foster","year":"1976","journal-title":"J. Oper. Res. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.dam.2012.08.032","article-title":"A set-covering based heuristic algorithm for the periodic vehicle routing problem","volume":"163","author":"Cacchiani","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.trb.2015.06.002","article-title":"A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem","volume":"79","author":"Bai","year":"2015","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_8","unstructured":"Vemuganti, R.R. (1998). Handbook of Combinatorial Optimization: Volume 1\u20133, Springer."},{"key":"ref_9","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Reducibility among Combinatorial Problems, Plenum Press."},{"key":"ref_10","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1287\/opre.25.5.760","article-title":"The set-covering problem: A new implicit enumeration algorithm","volume":"25","author":"Etcheberry","year":"1977","journal-title":"Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Balas, E., and Ho, A. (1980). Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study, Springer.","DOI":"10.1007\/BFb0120886"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0377-2217(87)90141-X","article-title":"An algorithm for set covering problem","volume":"31","author":"Beasley","year":"1987","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0377-2217(92)90215-U","article-title":"Enhancing an algorithm for set covering problems","volume":"58","author":"Beasley","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1287\/mnsc.36.6.674","article-title":"Optimal solution of set covering\/partitioning problems using dual heuristics","volume":"36","author":"Fisher","year":"1990","journal-title":"Manag. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1287\/opre.44.6.875","article-title":"A dynamic subgradient-based branch-and-bound procedure for set covering","volume":"44","author":"Balas","year":"1996","journal-title":"Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1023\/A:1019225027893","article-title":"Algorithms for the set covering problem","volume":"98","author":"Caprara","year":"2000","journal-title":"Ann. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chvatal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"ref_19","unstructured":"Kordalewski, D. (2013). New greedy heuristics for set cover and set packing. arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wang, Y., Lu, J., and Chen, J. (2014, January 5\u20137). Ts-ids algorithm for query selection in the deep web crawling. Proceedings of the Web Technologies and Applications: 16th Asia-Pacific Web Conference, APWeb 2014, Changsha, China. Proceedings 16.","DOI":"10.1007\/978-3-319-11116-2_17"},{"key":"ref_21","unstructured":"Singhania, S. (2019). Variations in Greedy Approach to Set Covering Problem. [Ph.D. Thesis, University of Windsor (Canada)]."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","article-title":"Greedy randomized adaptive search procedures","volume":"6","author":"Feo","year":"1995","journal-title":"J. Glob. Optim."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1057\/palgrave.jors.2601366","article-title":"A probabilistic greedy search algorithm for combinatorial optimisation with application to the set covering problem","volume":"53","author":"Haouari","year":"2002","journal-title":"J. Oper. Res. Soc."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1002\/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2","article-title":"A lagrangian heuristic for set-covering problems","volume":"37","author":"Beasley","year":"1990","journal-title":"Nav. Res. Logist. NRL"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/S0377-2217(96)00050-1","article-title":"Simple Lagrangian heuristic for the set covering problem","volume":"97","author":"Haddadi","year":"1997","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","article-title":"A heuristic method for the set covering problem","volume":"47","author":"Caprara","year":"1999","journal-title":"Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/0377-2217(95)00159-X","article-title":"A genetic algorithm for the set covering problem","volume":"94","author":"Beasley","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1057\/palgrave.jors.2601317","article-title":"An indirect genetic algorithm for set covering problems","volume":"53","author":"Aickelin","year":"2002","journal-title":"J. Oper. Res. Soc."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1016\/j.ejor.2005.09.028","article-title":"An effective and simple heuristic for the set covering problem","volume":"176","author":"Lan","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Wool, A., and Grossman, T. (1997). Computational Experience with Approxima-Tion Algorithms for the Set Covering Problem, Elsevier.","DOI":"10.1016\/S0377-2217(96)00161-0"},{"key":"ref_31","first-page":"1","article-title":"Solution Techniques for the Large Set Covering Problem","volume":"7112440","author":"Galinier","year":"2003","journal-title":"Les Cah. Du GERAD ISSN"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.eswa.2016.10.054","article-title":"Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization","volume":"70","author":"Crawford","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_33","first-page":"345","article-title":"A hybrid heuristic for the set covering problem","volume":"12","author":"Sundar","year":"2012","journal-title":"Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Maneengam, A., and Udomsakdigool, A. (2021). A set covering model for a green ship routing and scheduling problem with berth time-window constraints for use in the bulk cargo industry. Appl. Sci., 11.","DOI":"10.3390\/app11114840"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Derpich, I., Valencia, J., and Lopez, M. (2023). The set covering and other problems: An empiric complexity analysis using the minimum ellipsoidal width. Mathematics, 11.","DOI":"10.3390\/math11132794"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Borda, M. (2011). Fundamentals in Information Theory and Coding, Springer Science & Business Media.","DOI":"10.1007\/978-3-642-20347-3"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"OR-Library: Distributing test problems by electronic mail","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/7\/321\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T20:03:56Z","timestamp":1760126636000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/7\/321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,29]]},"references-count":37,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,7]]}},"alternative-id":["a16070321"],"URL":"https:\/\/doi.org\/10.3390\/a16070321","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,29]]}}}