EUVIMEDEUVIMED entdecken
Crossref

A Graph-Based Neural Approach to Linear Sum Assignment Problems

Carlo Aironi iD, Samuele Cornell iD, Stefano Squartini iD

International Journal of Neural Systems · 2024

DOI: 10.1142/s0129065724500114 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Neural Systems, 2024. Verfasst von Carlo Aironi und 2 weiteren Autor:innen. Beteiligte Einrichtung: Department of Information Engineering, Università Politecnica delle Marche, Italy. Hauptthemen laut MEDLINE: Learning, Algorithms. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 81 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 .

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

LearningAlgorithmsReproducibility of ResultsComputer SimulationNeural Networks, Computer

Stichwörter der Autor:innen

Linear sum assignmentdeep neural networksgraph neural networkssmart grid optimizationsmart meters scheduling

Autor:innen und Institutionen

  • Department of Information Engineering, Università Politecnica delle Marche, Italy.

ORCID-Profile: Carlo Aironi, Samuele Cornell, Stefano Squartini

Zitieren

APA

Aironi, C., Cornell, S., & Squartini, S. (2024). A Graph-Based Neural Approach to Linear Sum Assignment Problems. International Journal of Neural Systems. https://doi.org/10.1142/s0129065724500114

Vancouver

Aironi C, Cornell S, Squartini S. A Graph-Based Neural Approach to Linear Sum Assignment Problems. International Journal of Neural Systems. 2024. doi:10.1142/s0129065724500114

BibTeX
@article{Aironi2024,
  author = {Aironi, Carlo and Cornell, Samuele and Squartini, Stefano},
  title = {A Graph-Based Neural Approach to Linear Sum Assignment Problems},
  journal = {International Journal of Neural Systems},
  year = {2024},
  doi = {10.1142/s0129065724500114}
}
Kostenlos starten →