Learning to Solve NP-Complete Problems - A Graph Neural Network for the Decision TSP

By Marcelo O. R. Prates, Pedro H. C. Avelar, Henrique Lemos, L. C. Lamb, Moshe Y. Vardi. 2018

206 citations recorded by the source corpus.

Graph Neural Networks (GNN) are a promising technique for bridging differential programming and combinatorial domains. GNNs employ trainable modules which can be assembled in different configurations that reflect the relational structure of each problem instance. In this paper, we show that GNNs can learn to solve, with very little supervision, the decision variant of the Traveling Salesperson Problem (TSP), a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in which edges (embedded with their weights) communicate with vertices for a number of iterations after which the model is asked to decide whether a route with cost < C exists. We show that such a network can be trained with sets of dual examples: given the optimal tour cost C∗, we produce one decision instance with target cost x% smaller and one with target cost x% larger than C∗. We were able to obtain 80% accuracy training with −2%,+2% deviations, and the same trained model can generalize for more relaxed deviations with increasing performance. We also show that the model is capable of generalizing for larger problem sizes. Finally, we provide a method for predicting the optimal route cost within 2% deviation from the ground truth. In summary, our work shows that Graph Neural Networks are powerful enough to solve NP-Complete problems which combine symbolic and numeric data.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs (2018, methodology): “[31], the decision version of the traveling salesman problem [38], graph colouring [26], and clique optimisation [19].”
Fast and flexible design of novel proteins using graph neural networks (2019, methodology): “In order to facilitate this search, we focused on designing a neural network capable of solving Sudoku puzzles, which is a well-defined CSP ( 25 ) for which predictions made by the network can easily be verified.”
Deep Learning on Graphs: A Survey (2018, unknown): “Besides standard graph inference tasks such as node or graph classification, graph-based deep learning methods have also been applied to a wide range of disciplines, such as modeling social influence [103], recommendation [51], [78], [96], chemistry [37], [41], [50], [98], [99], physics [104], [105]”
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “This is expected, since SAT and TSP are NP-complete and are hard to approximate with strong guarantees.”
Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning (2021, unknown): “There have been few studies that employ graph neural networks (GNN) to solve scheduling problems, such as travelling salesman problem (TSP), vehicle routing problems (VRP) (Li, Chen, and Koltun 2018; Kaempfer and Wolf 2018; Prates et al. 2019).”
Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “To do so, they represent QAP instances as two adjacency matrices, and use the two corresponding graphs as input to a GNN. Prates et al. [2019] train a GNN in a supervised manner to predict the satisﬁability of the decision version of the TSP, considering instances up to 105 cities.”
Neurosymbolic AI: the 3rd wave (2020, background): “…AI, including logical neural networks, logic tensor networks and extensions thereof to cater for probabilistic languages and neural probabilistic logic programming (Serafini and d’Avila Garcez 2016; Stehr et al. 2022; Lamb et al. 2020; Prates et al. 2019; Riegel et al. 2020; Manhaeve et al. 2018).”
Learning to simulate and design for structural engineering (2020, background): “Though some papers have applied GNNs to solve combinatorial optimization problems (Bello et al., 2016; Kool et al., 2018; Prates et al., 2019; Li et al., 2018), applying GNN to solve design optimization problem is underexplored.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “) can be expressed in terms of graphs and more recently, there has been interest in leveraging graph embeddings to approximate solutions of NP-hard problems (Khalil et al., 2017; Nowak et al., 2017; Selsam et al., 2018; Prates et al., 2019).”