Linear Assignment Problems are fundamental combinatorial optimization problems that appear throughout domains such as logistics, robotics and telecommunications. In general, solving assignment problems to optimality is computationally infeasible even for contexts of small dimensionality, and so heuristic algorithms are often employed to find near-optimal solutions. The handcrafting of a heuristic usually requires expert-knowledge to exploit the problem structure to be addressed, however if the problem description changes slightly, a previously derived heuristic may no longer be appropriate. This work explores a more general-purpose learning approach, based on the description of the problem through a bipartite graph, and the use of a Message Passing Graph Neural Network model, to attain the correct assignment permutation. The simulation results indicate that the proposed structure allows for a significant increase in classification accuracy if compared with two different DNN approaches based on Dense Networks and Convolutional Neural Networks, furthermore, the GNN has proved to be very efficient with regard to the processing time and memory requirements, thanks to intrinsic parameter-sharing capability.

Tackling the Linear Sum Assignment Problem with Graph Neural Networks / Aironi, Carlo; Cornell, Samuele; Squartini, Stefano. - 1724:(2022), pp. 90-101. (Intervento presentato al convegno AII 2022) [10.1007/978-3-031-24801-6_7].

Tackling the Linear Sum Assignment Problem with Graph Neural Networks

Aironi, Carlo;Cornell, Samuele;Squartini, Stefano
2022-01-01

Abstract

Linear Assignment Problems are fundamental combinatorial optimization problems that appear throughout domains such as logistics, robotics and telecommunications. In general, solving assignment problems to optimality is computationally infeasible even for contexts of small dimensionality, and so heuristic algorithms are often employed to find near-optimal solutions. The handcrafting of a heuristic usually requires expert-knowledge to exploit the problem structure to be addressed, however if the problem description changes slightly, a previously derived heuristic may no longer be appropriate. This work explores a more general-purpose learning approach, based on the description of the problem through a bipartite graph, and the use of a Message Passing Graph Neural Network model, to attain the correct assignment permutation. The simulation results indicate that the proposed structure allows for a significant increase in classification accuracy if compared with two different DNN approaches based on Dense Networks and Convolutional Neural Networks, furthermore, the GNN has proved to be very efficient with regard to the processing time and memory requirements, thanks to intrinsic parameter-sharing capability.
2022
978-3-031-24800-9
978-3-031-24801-6
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11566/310929
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact