A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Combines TSP and SC to solve real-world vaccine distribution.
Structure learning of Bayesian networks is an important problem that arises in numerous machine learning applications. In this work, we present a novel approach for learning the structure of Bayesian networks using the solution of an appropriately constructed traveling salesman problem. In our approach, one computes an…
In this paper a highly abstracted view on the historical development of Genetic Algorithms for the Traveling Salesman Problem is given. In a meta-data analysis three phases in the development can be distinguished. First exponential growth in interest till 1996 can be observed, growth stays linear till 2011 and after th…
We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models on fixed graph sizes up to 100 nodes, and evaluate them on variable sized graphs up to 500 nodes. Be…
Deep RL learns 2-opt heuristics to improve TSP solutions.
This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach ou…
Machine learning reduces combinatorial optimization problem dimensions.
A new scheme reduces global search cost by a square root factor.
Two DRL policies collaborate to solve NP-hard routing problems.
Sym-NCO leverages symmetricities to improve DRL-NCO performance.
Linear-time graph optimization using reinforcement learning.
Equity-Transformer solves NP-hard min-max routing problems efficiently.
Deep learning has been extended to a number of new domains with critical success, though some traditional orienteering problems such as the Travelling Salesman Problem (TSP) and its variants are not commonly solved using such techniques. Deep neural networks (DNNs) are a potentially promising and under-explored solutio…
In this paper we introduce a new neural architecture for sorting unordered sequences where the correct sequence order is not easily defined but must rather be inferred from training data. We refer to this architecture as OrderNet and describe how it was constructed to be naturally permutation equivariant while still al…
DeepCO uses deep learning for offline combinatorial optimization in warehouse operations.
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative t…
Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such a…
In this work, we provide theoretical guarantees for reward decomposition in deterministic MDPs. Reward decomposition is a special case of Hierarchical Reinforcement Learning, that allows one to learn many policies in parallel and combine them into a composite solution. Our approach builds on mapping this problem into a…
When a black-box optimization objective can only be evaluated with costly or noisy measurements, most standard optimization algorithms are unsuited to find the optimal solution. Specialized algorithms that deal with exactly this situation make use of surrogate models. These models are usually continuous and smooth, whi…
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention …
Bayesian optimization method for permutations accelerates combinatorial search.
In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to…
The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case t…
DPDP combines neural heuristics with DP for vehicle routing problems.
New research shows deep learning struggles with hard problems due to biased data generation.
Adversarial self-play in two-player games has delivered impressive results when used with reinforcement learning algorithms that combine deep neural networks and tree search. Algorithms like AlphaZero and Expert Iteration learn tabula-rasa, producing highly informative training data on the fly. However, the self-play t…
This paper explores the possibility of near-optimally solving multi-agent, multi-task NP-hard planning problems with time-dependent rewards using a learning-based algorithm. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problem…
New framework analyzes effectiveness of neural network-based combinatorial problem solvers.
We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. Such problems cannot be trivially addressed by existent approaches such as sequence-to-sequence and Neural Turing Machines, because th…
Study shows stability of travel time data reconstruction from closed subsets.
New L2D framework allows deferring specific parts of a sequence prediction to experts.
Study travel time tomography for transversely isotropic media using modified pseudodifferential calculus.
New proofs confirm travel time data determine simple metrics on a disc.
Paper addresses travel time tomography stability and statistical inversion.
Study on travel time formulas in a lake with wind flow.
We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an -vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to $\calP_n$ for edges in the cycle and $\calQ_n$ otherwise. This …
This study uses Twitter to analyze traveler behavior in Manhattan.
We show that the travel time difference functions, measured on the boundary, determine a compact Riemannian manifold with smooth boundary up to Riemannian isometry, if boundary satisfies a certain visibility condition. This corresponds with the inverse microseismicity problem. The novelty of our paper is a new type of …
Simultaneously estimates travel times and route choice model parameters.
Estimating temporal patterns in travel times along road segments in urban settings is of central importance to traffic engineers and city planners. In this work, we propose a methodology to leverage coarse-grained and aggregated travel time data to estimate the street-level travel times of a given metropolitan area. Ou…
Study highlights fairness issues in travel behavior prediction models.
Bayesian calibration improves ABMs for predicting travel patterns.
Researchers recover Riemannian manifolds and lower order terms from travel time data.
The Euclidean traveller explores various geometric spaces, seeing different places in each.
Resolving Schwartz's quadratic meander number conjecture
New model predicts travel demand uncertainty with high accuracy.
A new clustering framework optimizes customer search data for personalized travel recommendations.
The goal of Machine Learning to automatically learn from data, extract knowledge and to make decisions without any human intervention. Such automatic (aML) approaches show impressive success. Recent results even demonstrate intriguingly that deep learning applied for automatic classification of skin lesions is on par w…