POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

Abstract

In neural combinatorial optimization (CO), reinforcement learning (RL) can turn a deep neural net into a fast, powerful heuristic solver of NP-hard problems. This approach has a great potential in practical applications because it allows near-optimal solutions to be found without expert guides armed with substantial domain knowledge. We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. POMO uses a modified REINFORCE algorithm that forces diverse rollouts towards all optimal solutions. Empirically, the low-variance baseline of POMO makes RL training fast and stable, and it is more resistant to local minima compared to previous approaches. We also introduce a new augmentation-based inference method, which accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based on POMO shows a significant improvement in performance over all recent learned heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100 while reducing inference time by more than an order of magnitude.

Accepted at NeurIPS 2020

References in corpus (5)

• Sequence to Sequence Learning with Neural Networks
• Neural Combinatorial Optimization with Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• Learning Improvement Heuristics for Solving Routing Problems

Cited by in corpus (9)

• Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions
• Neural Airport Ground Handling
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems
• RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning
• Learning for routing: A guided review of recent developments and future directions
• Hierarchical Neural Constructive Solver for Real-world TSP Scenarios
• Learning to Delegate for Large-scale Vehicle Routing