Can Latent Space Search Adapt Policies for Combinatorial Optimization?

Original title: Combinatorial Optimization with Policy Adaptation using Latent Space Search

Authors: Felix Chalumeau, Shikha Surana, Clement Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, Thomas D. Barrett

The article tackles the challenge of solving complex Combinatorial Optimization problems. Reinforcement Learning (RL) has potential, yet it hasn’t replaced industrial solvers. Current methods rely on limited search strategies or computationally expensive fine-tuning. Enter COMPASS: a new RL approach that anticipates effective search during pre-training. It uses a diverse set of specialized policies, shaped by a continuous latent space. Evaluating COMPASS across Traveling Salesman, Vehicle Routing, and Job-Shop Scheduling problems, the study reveals two major wins. First, COMPASS outperforms existing methods on 11 standard benchmarks. Second, it shows superior generalization, surpassing other approaches across 18 transformed instance distributions. COMPASS demonstrates promising potential in improving problem-solving strategies, highlighting its ability to handle various Combinatorial Optimization challenges efficiently.

Original article: https://arxiv.org/abs/2311.13569