{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T16:43:53Z","timestamp":1778085833117,"version":"3.51.4"},"reference-count":81,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Neur. Syst."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p> Linear assignment problems are well-known combinatorial optimization problems involving domains such as logistics, robotics and telecommunications. In general, obtaining an optimal solution to such problems is computationally infeasible even in small settings, so heuristic algorithms are often used to find near-optimal solutions. In order to attain the right assignment permutation, this study investigates a general-purpose learning strategy that uses a bipartite graph to describe the problem structure and a message passing Graph Neural Network (GNN) model to learn the correct mapping. Comparing the proposed structure with two existing DNN solutions, simulation results show that the proposed approach significantly improves classification accuracy, proving to be very efficient in terms of processing time and memory requirements, due to its inherent parameter sharing capability. Among the many practical uses that require solving allocation problems in everyday scenarios, we decided to apply the proposed approach to address the scheduling of electric smart meters access within an electricity distribution smart grid infrastructure, since near-real-time energy monitoring is a key element of the green transition that has become increasingly important in recent times. The results obtained show that the proposed graph-based solver, although sub-optimal, exhibits the highest scalability, compared with other state-of-the-art heuristic approaches. To foster the reproducibility of the results, we made the code available at https:\/\/github.com\/aircarlo\/GNN_LSAP . <\/jats:p>","DOI":"10.1142\/s0129065724500114","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T07:29:49Z","timestamp":1702366189000},"source":"Crossref","is-referenced-by-count":4,"title":["A Graph-Based Neural Approach to Linear Sum Assignment Problems"],"prefix":"10.1142","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5754-4864","authenticated-orcid":false,"given":"Carlo","family":"Aironi","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Universit\u00e0 Politecnica delle Marche, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5358-1844","authenticated-orcid":false,"given":"Samuele","family":"Cornell","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Universit\u00e0 Politecnica delle Marche, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9374-0128","authenticated-orcid":false,"given":"Stefano","family":"Squartini","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Universit\u00e0 Politecnica delle Marche, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2024,1,17]]},"reference":[{"key":"S0129065724500114BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3023-4_2"},{"key":"S0129065724500114BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2020.107322"},{"key":"S0129065724500114BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2014.09.015"},{"key":"S0129065724500114BIB004","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.453"},{"key":"S0129065724500114BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(85)90153-7"},{"key":"S0129065724500114BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2014.2363092"},{"key":"S0129065724500114BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2017.2689760"},{"key":"S0129065724500114BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2016.2530061"},{"key":"S0129065724500114BIB009","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2017.7952154"},{"key":"S0129065724500114BIB010","doi-asserted-by":"publisher","DOI":"10.1109\/ASRU46091.2019.9003959"},{"key":"S0129065724500114BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/SLT48900.2021.9383490"},{"key":"S0129065724500114BIB012","doi-asserted-by":"publisher","DOI":"10.21437\/CHiME.2020-1"},{"key":"S0129065724500114BIB013","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"S0129065724500114BIB014","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"S0129065724500114BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186476"},{"key":"S0129065724500114BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582905"},{"key":"S0129065724500114BIB018","first-page":"431","volume-title":"Network Flows and Matching","author":"Ramakrishnan K.","year":"1991"},{"key":"S0129065724500114BIB019","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/1991250404031"},{"key":"S0129065724500114BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"S0129065724500114BIB021","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199203)39:2<137::AID-NAV3220390202>3.0.CO;2-D"},{"key":"S0129065724500114BIB022","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1090\/dimacs\/040\/17","volume-title":"Network Design: Connectivity and Facilities Location","volume":"40","author":"Murphey R. A.","year":"1997"},{"key":"S0129065724500114BIB023","first-page":"9999","volume-title":"7th Int. Conf. Numerical Analysis and Applied Mathematics","author":"Naiem A.","year":"2009"},{"key":"S0129065724500114BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2013.54"},{"key":"S0129065724500114BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/SPAWC.2017.8227766"},{"key":"S0129065724500114BIB026","doi-asserted-by":"publisher","DOI":"10.1109\/ICCW.2018.8403662"},{"key":"S0129065724500114BIB027","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2866382"},{"key":"S0129065724500114BIB028","doi-asserted-by":"publisher","DOI":"10.1109\/ChiCC.2015.7260186"},{"key":"S0129065724500114BIB029","doi-asserted-by":"publisher","DOI":"10.1109\/LWC.2018.2843359"},{"key":"S0129065724500114BIB030","doi-asserted-by":"publisher","DOI":"10.3390\/app9173470"},{"key":"S0129065724500114BIB031","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.00682"},{"key":"S0129065724500114BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-24801-6_7"},{"key":"S0129065724500114BIB033","series-title":"Massachusetts Institute of Technology","volume-title":"The Hungarian Algorithm for Weighted Bipartite Graphs","author":"Grinman A.","year":"2015"},{"key":"S0129065724500114BIB034","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00133"},{"key":"S0129065724500114BIB035","doi-asserted-by":"publisher","DOI":"10.1145\/3326362"},{"key":"S0129065724500114BIB036","first-page":"4558","volume-title":"2018 IEEE\/CVF Conf. Computer Vision and Pattern Recognition","volume":"1","author":"Landrieu L.","year":"2017"},{"key":"S0129065724500114BIB038","volume-title":"Proc. 5th Int. Conf. Learning Representations","author":"Kipf T. N.","year":"2017"},{"key":"S0129065724500114BIB039","first-page":"1025","volume":"30","author":"Hamilton W.","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"S0129065724500114BIB040","volume-title":"Int. Conf. Learning Representations","author":"Li Y.","year":"2018"},{"key":"S0129065724500114BIB041","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/505"},{"key":"S0129065724500114BIB042","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219890"},{"key":"S0129065724500114BIB043","series-title":"Proceedings of Machine Learning Research","first-page":"1263","volume-title":"Proc. 34th Int. Conf. Machine Learning","volume":"70","author":"Gilmer J.","year":"2017"},{"key":"S0129065724500114BIB044","first-page":"6533","volume":"30","author":"Fout A.","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"S0129065724500114BIB045","first-page":"606","volume":"34","author":"Choi E.","year":"2020","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"S0129065724500114BIB046","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2012.04.025"},{"key":"S0129065724500114BIB047","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065723500466"},{"key":"S0129065724500114BIB048","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065722500502"},{"key":"S0129065724500114BIB049","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065723500557"},{"key":"S0129065724500114BIB050","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065723500429"},{"key":"S0129065724500114BIB051","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065722500034"},{"key":"S0129065724500114BIB052","doi-asserted-by":"publisher","DOI":"10.1007\/s00702-010-0450-3"},{"key":"S0129065724500114BIB053","doi-asserted-by":"publisher","DOI":"10.1177\/1550059411428555"},{"key":"S0129065724500114BIB054","doi-asserted-by":"publisher","DOI":"10.1016\/j.neulet.2017.04.009"},{"key":"S0129065724500114BIB055","first-page":"616","volume":"23","author":"delEtoile J.","year":"2017","journal-title":"Neurosci.: A Rev. J. Bringing Neurobiol. Neurol. Psych."},{"key":"S0129065724500114BIB056","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2022.3190448"},{"key":"S0129065724500114BIB057","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065721500477"},{"key":"S0129065724500114BIB058","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2005.1555942"},{"key":"S0129065724500114BIB059","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"S0129065724500114BIB060","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/595"},{"key":"S0129065724500114BIB061","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014731"},{"key":"S0129065724500114BIB062","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2019.00125"},{"key":"S0129065724500114BIB065","first-page":"13","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Li Z.","year":"2018"},{"key":"S0129065724500114BIB066","series-title":"Proceedings of Machine Learning Research","first-page":"3835","volume-title":"Proc. 36th Int. Conf. Machine Learning","volume":"97","author":"Li Y.","year":"2019"},{"key":"S0129065724500114BIB067","first-page":"1220","volume-title":"Int. Conf. Learning Representations","author":"Fey M.","year":"2020"},{"key":"S0129065724500114BIB068","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5720"},{"key":"S0129065724500114BIB072","first-page":"15","volume-title":"International Conf. Learning Representations","author":"Kingma D.","year":"2014"},{"key":"S0129065724500114BIB077","doi-asserted-by":"publisher","DOI":"10.3390\/en14030719"},{"key":"S0129065724500114BIB078","doi-asserted-by":"publisher","DOI":"10.1002\/9781119360124.ch8"},{"key":"S0129065724500114BIB079","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2998100"},{"key":"S0129065724500114BIB080","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2009.08.015"},{"key":"S0129065724500114BIB081","doi-asserted-by":"publisher","DOI":"10.4108\/eai.7-8-2017.152985"},{"key":"S0129065724500114BIB082","doi-asserted-by":"publisher","DOI":"10.1109\/SmartGridComm.2018.8587478"},{"key":"S0129065724500114BIB083","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.10.006"},{"key":"S0129065724500114BIB084","doi-asserted-by":"publisher","DOI":"10.1145\/938985.938993"},{"key":"S0129065724500114BIB085","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1208720"},{"key":"S0129065724500114BIB086","first-page":"631","volume-title":"2nd Int. Conf. Broadband Networks","author":"Zhang J.","year":"2005"},{"key":"S0129065724500114BIB087","doi-asserted-by":"publisher","DOI":"10.1109\/WPMC55625.2022.10014735"},{"key":"S0129065724500114BIB088","volume-title":"What Smart Meters Can Tell Us: Insights on Electricity Supply and Use in Mathura and Bareilly Households: Report","author":"Agrawal S.","year":"2020"},{"key":"S0129065724500114BIB089","first-page":"99","volume-title":"ITG Conf. Speech Communication","author":"von Neumann T.","year":"2021"},{"key":"S0129065724500114BIB090","doi-asserted-by":"publisher","DOI":"10.21437\/Interspeech.2019-1827"},{"key":"S0129065724500114BIB091","doi-asserted-by":"publisher","DOI":"10.21437\/Interspeech.2021-493"},{"key":"S0129065724500114BIB092","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV48922.2021.01334"}],"container-title":["International Journal of Neural Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129065724500114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T08:10:03Z","timestamp":1708330203000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129065724500114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,17]]},"references-count":81,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["10.1142\/S0129065724500114"],"URL":"https:\/\/doi.org\/10.1142\/s0129065724500114","relation":{},"ISSN":["0129-0657","1793-6462"],"issn-type":[{"value":"0129-0657","type":"print"},{"value":"1793-6462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,17]]},"article-number":"2450011"}}