Застосування методу згорткових нейронних мереж на графах для розв’язання задачі комівояжера

Abstract

Integer programming problem is NP-complete which leads to difficulties in obtaining exact solution at large scales. The Travelling Salesman Problem (TSP) is a famous example, asking for the shortest possible route that visits each city and returns to the origin city. This problem can be represented as sequential decision making tasks on graphs, making them a good fit for machine learning approaches, such as graph neural networks, and potentially give a possibility to avoids expensive or specialized handcrafted solutions.