Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem
This work addresses the problem of slow and compute-intensive deep learning solutions for combinatorial optimization, offering a faster inference method for researchers and practitioners in optimization and AI.
The paper tackles the scalability issue of exact algorithms for the Traveling Salesman Problem by integrating entropic regularized optimal transport into a deep reinforcement learning network, resulting in a model that learns without supervision and infers significantly faster than current autoregressive approaches.
The traveling salesman problem is a fundamental combinatorial optimization problem with strong exact algorithms. However, as problems scale up, these exact algorithms fail to provide a solution in a reasonable time. To resolve this, current works look at utilizing deep learning to construct reasonable solutions. Such efforts have been very successful, but tend to be slow and compute intensive. This paper exemplifies the integration of entropic regularized optimal transport techniques as a layer in a deep reinforcement learning network. We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches. We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training.