POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
By Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Seungjai Min, Youngjune Gwon. Neural Information Processing Systems, 2020
645 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Automotive Engineering, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/246a68fcf2bcd1db8f0184129b63123d1f98eaa3
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
Citations in the corpus
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, methodology): “In our evaluation, we compared our EoH-designed GLS against various neural solvers such as AM, POMO, and LEHD, as well as different GLS algorithms including GNNGLS, NeuralGLS, LS, GLS, EBGLS, and KGLS.”
- Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning (2023, neutral): “1 3) Baselines: The learned FJSP scheduling policies are compared to four well-known PDRs that work well in practice, including FIFO, most operations remaining (MOR), shortest processing time (SPT), and most work remaining (MWKR) [35], [44].”