Efficient Active Search for Combinatorial Optimization Problems

Abstract

Recently numerous machine learning based methods for combinatorial optimization problems have been proposed that learn to construct solutions in a sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straightforward to integrate them into a high-level search procedure offering strong search guidance. Bello et al. (2016) propose active search, which adjusts the weights of a (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of a given model and outperform state-of-the-art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.

arXiv commentAccepted at ICLR 2022

References in corpus (10)

• Learning Combinatorial Optimization Algorithms over Graphs
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem
• Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention