Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

Combinatorial optimization algorithms for graph problems are usually designed\nafresh for each new problem with careful attention by an expert to the problem\nstructure. In this work, we develop a new framework to solve any combinatorial\noptimization problem over graphs that can be formulated as a single player game\ndefined by states, actions, and rewards, including minimum spanning tree,\nshortest paths, traveling salesman problem, and vehicle routing problem,\nwithout expert knowledge. Our method trains a graph neural network using\nreinforcement learning on an unlabeled training set of graphs. The trained\nnetwork then outputs approximate solutions to new graph instances in linear\nrunning time. In contrast, previous approximation algorithms or heuristics\ntailored to NP-hard problems on graphs generally have at least quadratic\nrunning time. We demonstrate the applicability of our approach on both\npolynomial and NP-hard problems with optimality gaps close to 1, and show that\nour method is able to generalize well: (i) from training on small graphs to\ntesting on large graphs; (ii) from training on random graphs of one type to\ntesting on random graphs of another type; and (iii) from training on random\ngraphs to running on real world graphs.\n