Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero

Abstract

There have been increasing challenges to solve combinatorial optimization problems by machine learning. Khalil et al. proposed an end-to-end reinforcement learning framework, S2V-DQN, which automatically learns graph embeddings to construct solutions to a wide range of problems. To improve the generalization ability of their Q-learning method, we propose a novel learning strategy based on AlphaGo Zero which is a Go engine that achieved a superhuman level without the domain knowledge of the game. Our framework is redesigned for combinatorial problems, where the final reward might take any real number instead of a binary response, win/lose. In experiments conducted for five kinds of NP-hard problems including {\sc MinimumVertexCover} and {\sc MaxCut}, our method is shown to generalize better to various graphs than S2V-DQN. Furthermore, our method can be combined with recently-developed graph neural network (GNN) models such as the \emph{Graph Isomorphism Network}, resulting in even better performance. This experiment also gives an interesting insight into a suitable choice of GNN models for each task.

References in corpus (9)

• Emergence of scaling in random networks
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Continuous control with deep reinforcement learning
• Neural Message Passing for Quantum Chemistry
• Learning Combinatorial Optimization Algorithms over Graphs
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Attention, Learn to Solve Routing Problems!
• Universal Invariant and Equivariant Graph Neural Networks

Cited by in corpus (12)

• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Generalized Planning With Deep Reinforcement Learning
• Exploratory Combinatorial Optimization with Reinforcement Learning
• Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Train on Small, Play the Large: Scaling Up Board Games with AlphaZero and GNN
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• Reinforcement Learning for Flexibility Design Problems
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems
• Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems