Learning to solve NP-complete problems

Abstract

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 thesis, we propose a new formulation for GNNs, which employs the concept of “types” to partition the objects in the problem domain into many distinct classes, yielding the Typed Graph Networks (TGN) model and a Python / Tensorflow library for prototyping TGNs. This thesis is also concerned with the application of GNNs to the Traveling Salesperson Problem (TSP). We show that GNNs can learn to solve, with very little supervision, the decision variant of the TSP, a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in graph in which edges from the input graph communicate with vertices from the input graph for a number of iterations after which the model is asked to decide whether a route with cost < C 2 R+ 0 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 (C) 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 1.5% relative 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, in addition to proposing a modern reformulation of the meta-model.

Graph Neural Networks (GNN) constituem uma técnica promisora para conectar programação diferencial e domínios combinatoriais. GNNs lançam mão de módulos treináveis os quais podem ser montados em diferentes configurações, cada uma refletindo a estrutura relacional de uma instância específica. Nessa tese, nós propomos uma nova formulação para GNNs, a qual faz uso do conceito de “tipos” para particionar os objetos no domínio do problema em múltiplas classes distintas, resultando no modelo das Typed Graph Networks (TGN) e numa biblioteca Python / Tensorflow para prototipar TGNs. Esta tese também se preocupa com a aplicação de GNNs no Problema do Caixeiro(a) Viajante (PCV). Nós mostramos que GNNs são capazes de aprender a resolver, com pouquíssima supervisão, a variante de decisão do PCV, um problema NP-Completo altamente relevante. Nosso modelo é treinado para funcionar, efetivamente, como um algoritmo de troca de mensagens em grafos no qual as arestas do grafo de entrada comunicam-se com os vértices do grafo de entrada por um determinado número de iterações, depois do qual o modelo é forçado a responder se o grafo de entrada admite ou não uma rota Hamiltoniana de custo < C 2 R+ 0 . Nós mostramos que esta rede pode ser treinada com conjuntos de exemplos duais: dado o custo ótimo C , produzimos uma instância de decisão com custo alvo (C) x% menor e uma com custo alvo x% maior do que C . Nós fomos capazes de obter 80% de acurácia treinando o modelo com desvios de −2%,+2%, e o mesmo modelo treinado foi capaz de generalizar para desvios mais relaxados com melhor performance. Também mostramos que o modelo é capaz de generalizar para problemas maiores. Finalmente, nós oferecemos um método para predizer o custo de rota ótimo dentro de 1.5% de desvio relativo para o valor real. Em resumo, nosso trabalho demonstra que GNNs são suficientemente poderosas para resolver problems NP-Completos que combinam dados simbólicos e numéricos, além de propor uma reformulação moderna do meta-modelo.