{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T08:49:03Z","timestamp":1780044543426,"version":"3.53.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031959752","type":"print"},{"value":"9783031959769","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-95976-9_12","type":"book-chapter","created":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T03:53:45Z","timestamp":1751082825000},"page":"191-208","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Accelerated Discovery of\u00a0Set Cover Solutions via\u00a0Graph Neural Networks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6154-1466","authenticated-orcid":false,"given":"Zohair","family":"Shafi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1649-1401","authenticated-orcid":false,"given":"Benjamin A.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1892-1188","authenticated-orcid":false,"given":"Tina","family":"Eliassi-Rad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2236-4406","authenticated-orcid":false,"given":"Rajmonda S.","family":"Caceres","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1038\/s42256-022-00589-y","volume":"5","author":"MC Angelini","year":"2023","unstructured":"Angelini, M.C., Ricci-Tersenghi, F.: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nat. Mach. Intell. 5(1), 29\u201331 (2023)","journal-title":"Nat. Mach. Intell."},{"issue":"11","key":"12_CR2","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. Eur. J. Oper. Res. 290(2), 405\u2013421 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bestuzheva, K., et al.: Enabling research through the SCIP optimization suite 8.0. ACM Trans. Math. Softw. 49(2) (2023)","DOI":"10.1145\/3585516"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Boisvert, L., Verhaeghe, H., Cappart, Q.: Towards a generic representation of combinatorial problems for learning-based approaches. In: CPAIOR (2024)","DOI":"10.1007\/978-3-031-60597-0_7"},{"key":"12_CR6","unstructured":"B\u00f6ther, M., Ki\u00dfig, O., Taraz, M., Cohen, S., Seidel, K., Friedrich, T.: What\u2019s wrong with deep learning in tree search for combinatorial optimization. In: ICLR (2021)"},{"key":"12_CR7","unstructured":"Cappart, Q., Ch\u00e9telat, D., Khalil, E.B., Lodi, A., Morris, C., Velickovic, P.: Combinatorial optimization and reasoning with graph neural networks. JMLR 24, 130\u20131 (2023)"},{"key":"12_CR8","unstructured":"Chen, Z., Liu, J., Wang, X., Yin, W.: On representing linear programs by graph neural networks. In: ICLR (2022)"},{"key":"12_CR9","unstructured":"Chitra, U., Raphael, B.: Random walks on hypergraphs with edge-dependent vertex weights. In: ICML, pp. 1172\u20131181 (2019)"},{"issue":"3","key":"12_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"12_CR11","unstructured":"Dai, H., Khalil, E.B., Zhang, Y., Dilkina, B., Song, L.: Learning combinatorial optimization algorithms over graphs. In: NeurIPS (2017)"},{"key":"12_CR12","unstructured":"Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: NeurIPS (2016)"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Ding, J.Y., et al.: Accelerating primal solution findings for mixed integer programs based on solution prediction. In: AAAI (2020)","DOI":"10.1609\/aaai.v34i02.5503"},{"key":"12_CR14","unstructured":"Gasse, M., Ch\u00e9telat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. In: NeurIPS (2019)"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Gilmore, P.C., Gomory, R.E.: A linear programming approach to the cutting-stock problem. Oper. Res. 849\u2013859 (1961)","DOI":"10.1287\/opre.9.6.849"},{"key":"12_CR16","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https:\/\/www.gurobi.com"},{"key":"12_CR17","unstructured":"Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: NeurIPS (2017)"},{"key":"12_CR18","unstructured":"Han, Q., et al.: A GNN-guided predict-and-search framework for mixed-integer linear programming. In: ICLR (2022)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Heydaribeni, N., Zhan, X., Zhang, R., Eliassi-Rad, T., Koushanfar, F.: Distributed constrained combinatorial optimization leveraging hypergraph neural networks. Nat. Mach. Intell. 1\u20139 (2024)","DOI":"10.21203\/rs.3.rs-3613917\/v1"},{"key":"12_CR20","unstructured":"Hu, C.: Assessing and enhancing graph neural networks for combinatorial optimization: novel approaches and application in maximum independent set problems. arXiv preprint arXiv:2411.05834 (2024)"},{"key":"12_CR21","unstructured":"Ireland, D., Montana, G.: Lense: learning to navigate subgraph embeddings for large-scale combinatorial optimisation. In: ICML (2022)"},{"key":"12_CR22","unstructured":"Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: ICLR (2017)"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Kruber, M., L\u00fcbbecke, M.E., Parmentier, A.: Learning when to use a decomposition. In: International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2017)","DOI":"10.1007\/978-3-319-59776-8_16"},{"issue":"3","key":"12_CR24","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1016\/j.ejor.2005.09.028","volume":"176","author":"G Lan","year":"2007","unstructured":"Lan, G., DePuy, G.W., Whitehouse, G.E.: An effective and simple heuristic for the set covering problem. Eur. J. Oper. Res. 176(3), 1387\u20131403 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"12_CR25","unstructured":"Li, Z., Chen, Q., Koltun, V.: Combinatorial optimization with graph convolutional networks and guided tree search. In: NeurIPS (2018)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Liu, D., Fischetti, M., Lodi, A.: Learning to search in local branching. In: AAAI (2022)","DOI":"10.1609\/aaai.v36i4.20294"},{"key":"12_CR27","unstructured":"Nair, V., et\u00a0al.: Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 (2020)"},{"key":"12_CR28","unstructured":"Numeroso, D., Bacciu, D., Veli\u010dkovi\u0107, P.: Dual algorithmic reasoning. In: ICLR (2023)"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Santana, \u00cd., Lodi, A., Vidal, T.: Neural networks for local search and crossover in vehicle routing: a possible overkill? In: CPAIOR (2023)","DOI":"10.1007\/978-3-031-33271-5_13"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Schuetz, M.J., Brubaker, J.K., Katzgraber, H.G.: Combinatorial optimization with physics-inspired graph neural networks. Nat. Mach. Intell. (2022)","DOI":"10.1103\/PhysRevResearch.4.043131"},{"key":"12_CR31","unstructured":"Shafi, Z., Miller, B.A., Chatterjee, A., Eliassi-Rad, T., Caceres, R.S.: Grasp: accelerating shortest path attacks via graph attention. arXiv preprint arXiv:2310.07980 (2023)"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Shen, Y., Sun, Y., Li, X., Eberhard, A., Ernst, A.: Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. In: AAAI (2022)","DOI":"10.1609\/aaai.v36i9.21230"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Tian, H., Medya, S., Ye, W.: Combhelper: a neural approach to reduce search space for graph combinatorial problems. In: AAAI (2024)","DOI":"10.1609\/aaai.v38i18.30070"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Tong, H., Faloutsos, C., Pan, J.Y.: Fast random walk with restart and its applications. In: ICDM (2006)","DOI":"10.1109\/ICDM.2006.70"},{"issue":"7","key":"12_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.patter.2021.100273","volume":"2","author":"P Veli\u010dkovi\u0107","year":"2021","unstructured":"Veli\u010dkovi\u0107, P., Blundell, C.: Neural algorithmic reasoning. Patterns 2(7), 100273 (2021)","journal-title":"Patterns"},{"key":"12_CR36","unstructured":"Veli\u010dkovi\u0107, P., Cucurull, G., Casanova, A., Romero, A., Li\u00f2, P., Bengio, Y.: Graph attention networks. In: ICLR (2018)"},{"key":"12_CR37","unstructured":"Verhaeghe, H., Cappart, Q., Pesant, G., Quimper, C.G.: Learning precedences for scheduling problems with graph neural networks. In: Constraint Programming (2024)"},{"issue":"201","key":"12_CR38","first-page":"1","volume":"22","author":"Y Wang","year":"2021","unstructured":"Wang, Y., Huang, H., Rudin, C., Shaposhnik, Y.: Understanding how dimension reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMAP, and PaCMAP for data visualization. JMLR 22(201), 1\u201373 (2021)","journal-title":"JMLR"},{"key":"12_CR39","unstructured":"Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? In: ICLR (2018)"},{"key":"12_CR40","unstructured":"Yau, M., Lu, E., Karalias, N., Xu, J., Jegelka, S.: Are graph neural networks optimal approximation algorithms? In: NeurIPS (2024)"},{"key":"12_CR41","unstructured":"Zhu, G.: A new view of classification in astronomy with the archetype technique: an astronomical case of the np-complete set cover problem. arXiv preprint arXiv:1606.07156 (2016)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-95976-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T06:00:08Z","timestamp":1777528808000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-95976-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031959752","9783031959769"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-95976-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"29 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne, VIC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2025","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}