Skip to content

Learning to solve Minimum Vertex Cover using Graph Convolutional Networks and RL

Notifications You must be signed in to change notification settings

orrivlin/MinimumVertexCover_DRL

Repository files navigation

MinimumVertexCover_DRL

Learning to tackle the Minimum Vertex Cover using Graph Convolutional Networks and RL

This repsitory contains a PyTorch implementation of an MVC environment, graph convolutional networks (using DGL) and an actor-critic algorithm. At each episode the algorithm is presented with a random Erdős-Rényi graph, with a specified number of nodes and probability of edge connection, and the neural network is trained using a simple actor-critic algorithm. This code requires installing DGL (Deep Graph Library).

I have also written a Medium article on the subject of reinforcement learning for combinatorial optimization, feel free to check it out.

Below are some comparisons of solutions created by the neural network policy (upper ones) and those created by a greedy heuristic (lower):

alt text


alt text


alt text

The yellow nodes are those chosen as part of the solution, and the darker ones were left out. During solution construction, nodes are added sequentialy until all edges are covered.

About

Learning to solve Minimum Vertex Cover using Graph Convolutional Networks and RL

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages