Combining Reinforcement Learning and Optimal Transport for the Traveling
Salesman Problem
- URL: http://arxiv.org/abs/2203.00903v1
- Date: Wed, 2 Mar 2022 07:21:56 GMT
- Title: Combining Reinforcement Learning and Optimal Transport for the Traveling
Salesman Problem
- Authors: Yong Liang Goh, Wee Sun Lee, Xavier Bresson, Thomas Laurent, Nicholas
Lim
- Abstract summary: 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.
- Score: 18.735056206844202
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: 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.
Related papers
- Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
This work proposes a novel Self-Improved Learning (SIL) method for better scalability of neural optimization.
We develop an efficient self-improved mechanism that enables direct model training on large-scale problem instances without any labeled data.
In addition, we design a linear attention complexity mechanism for the computation model to efficiently handle large-scale problem instances with low overhead.
arXiv Detail & Related papers (2024-03-28T16:46:53Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form.
This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method.
A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
arXiv Detail & Related papers (2023-12-28T23:15:18Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms.
Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return.
We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
arXiv Detail & Related papers (2023-02-02T18:27:20Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver.
This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
arXiv Detail & Related papers (2023-01-28T01:50:42Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems.
We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately.
Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
arXiv Detail & Related papers (2022-10-31T09:46:26Z) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
We consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to.
We demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework.
arXiv Detail & Related papers (2022-10-12T03:56:37Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
Vehicle routing is a well known class of NP-hard optimisation problems.
Recent work in reinforcement learning has been a promising alternative approach.
This paper proposes a hybrid approach that combines reinforcement learning, policy rollouts, and a satisfiability.
arXiv Detail & Related papers (2022-06-14T06:27:09Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
This paper presents a new reinforcement learning approach that is based on entropy.
In addition, we design an off-policy-based reinforcement learning technique that maximises the expected return.
We show that our model can generalise to various route problems.
arXiv Detail & Related papers (2022-05-31T09:51:48Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
Vehicle routing problem (VRP) is a typical discrete optimization problem.
Many studies consider learning-based optimization algorithms to solve VRP.
This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
arXiv Detail & Related papers (2021-07-15T02:13:03Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together.
The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively.
Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
arXiv Detail & Related papers (2021-03-10T03:16:12Z) - Deep Reinforcement Learning for Combinatorial Optimization: Covering
Salesman Problems [4.692304496312442]
This paper introduces a new deep learning approach to approximately solve the Covering Salesman Problem (CSP)
In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution.
It is trained using the deep reinforcement learning without supervision.
arXiv Detail & Related papers (2021-02-11T07:25:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.