A Graph-Based Neural Approach to Linear Sum Assignment Problems.

Area of Science:

• Combinatorial Optimization
• Machine Learning
• Graph Neural Networks

Background:

• Linear assignment problems are computationally challenging, often requiring heuristic solutions.
• Existing deep neural network (DNN) approaches have limitations in efficiency and accuracy.
• Smart grids require efficient solutions for tasks like electric smart meter scheduling.

Purpose of the Study:

• To develop a general-purpose learning strategy for linear assignment problems using Graph Neural Networks (GNNs).
• To improve classification accuracy and computational efficiency compared to existing DNN methods.
• To apply the GNN approach to optimize electric smart meter scheduling in smart grids.

Main Methods:

• Utilized a bipartite graph to model the problem structure.
• Employed a message-passing Graph Neural Network (GNN) for learning optimal assignments.
• Compared the GNN approach against two existing DNN solutions through simulations.

Main Results:

• The proposed GNN model significantly improved classification accuracy over existing DNNs.
• The GNN approach demonstrated superior efficiency in processing time and memory usage due to parameter sharing.
• The graph-based solver exhibited high scalability for smart grid applications, outperforming other heuristic methods.

Conclusions:

• The GNN-based strategy provides an effective and efficient solution for linear assignment problems.
• The approach is highly scalable and suitable for complex, real-world applications like smart grid management.
• The study offers a reproducible GNN solution for combinatorial optimization challenges.