Reversible Action Design for Combinatorial Optimization with Reinforcement Learning

Abstract

Combinatorial optimization problem (COP) over graphs is a fundamental challenge in optimization. Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems and has demonstrated promising results. However, most RL solutions employ a greedy manner to construct the solution incrementally, thus inevitably pose unnecessary dependency on action sequences and need a lot of problem-specific designs. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs. Specifically, we define state as a solution to a problem instance and action as a perturbation to this solution. We utilize graph neural networks (GNN) to extract latent representations for given problem instances for state-action encoding, and then apply deep Q-learning to obtain a policy that gradually refines the solution by flipping or swapping vertex labels. Experiments are conducted on Maximum $k$-Cut and Traveling Salesman Problem and performance improvement is achieved against a set of learning-based and heuristic baselines.

References in corpus (7)

• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Q-Learning in enormous action spaces via amortized approximate maximization
• Exploratory Combinatorial Optimization with Reinforcement Learning
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• PiNet: A Permutation Invariant Graph Neural Network for Graph Classification