Νευρωνικά Δίκτυα Γράφων για την επίλυση του προβλήματος του περιπλανώμενου πωλητή : συνδυασμός μαθηματικού προγραμματισμού και μηχανικής μάθησης
Graph Neural Networks for solving the traveling salesman problem : combining mathematical programming and machine learning
View/
Keywords
TSP ; Traveling salesperson problem ; Graph Neural Network ; Integer linear programming ; Πρόβλημα του περιπλανώμενου πωλητή ; Ακεραιος προγραμματισμός ; Νευρωνικα Δίκτυα Γράφων ; GATAbstract
This dissertation examines the use of Graph Neural Networks (GNNs) for solving the classical Traveling Salesman Problem (TSP). The TSP is one of the well-known combinatorial optimization problems and is classified as NP-hard. The methodology developed in this work combines traditional optimization techniques with modern machine learning approaches, highlighting the role of Graph Neural Networks in modeling graph structures and addressing combinatorial problems. Specifically, the application of GNNs to the TSP aims at predicting the edges that form the optimal route in fully connected graphs. The training and evaluation of the Graph Neural Network models were conducted using synthetically generated data. The experimental results demonstrate that GNN models can be effectively trained to capture the patterns underlying optimal solutions and generalize to new instances, confirming their potential for handling complex optimization problems.
Postgraduate Studies Programme
Κυβερνοασφάλεια και Επιστήμη ΔεδομένωνDepartment
Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα ΠληροφορικήςNumber of pages
46Language
GreekCollections
Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού 3.0 Ελλάδα
Αναφορά Δημιουργού 3.0 Ελλάδα