Optimal transport with constraints: from mirror descent to classical mechanics

Abstract

Finding optimal trajectories for multiple traffic demands in a congested network is a challenging task. Optimal transport theory is a principled approach that has been used successfully to study various transportation problems. Its usage is limited by the lack of principled and flexible ways to incorporate realistic constraints. We propose a principled physics-based approach to impose constraints flexibly in such optimal transport problems. Constraints are included in mirror descent dynamics using the principle of D'Alembert-Lagrange from classical mechanics. This leads to a sparse, local and linear approximation of the feasible set leading in many cases to closed-form updates.

6 pages, 3 figures

References in corpus (23)

• Damage and fluctuations induce loops in optimal transport networks
• Transport on coupled spatial networks
• Entropy Rate of Diffusion Processes on Complex Networks
• Congestion induced by the structure of multiplex networks
• Structure, Scaling and Phase Transition in the Optimal Transport Network
• Global Optimization, Local Adaptation, and the Role of Growth in Distribution Networks
• Searchability of Networks
• Minimum spanning trees on random networks
• Hide and seek on complex networks
• Jamming transition in air transportation networks
• From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
• Stability of shortest paths in complex networks with random edge weights
• Statistical Mechanics of Steiner trees
• Comprehensive routing strategy on multilayer networks
• The Competition for Shortest Paths on Sparse Graphs
• Optimal transport in multilayer networks for traffic flow optimization
• Designing optimal networks for multi-commodity transport problem
• Network extraction by routing optimization
• Sustainable optimal transport in multilayer networks
• Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
• Noise-induced network topologies
• A Laplacian Approach to ${\ell }_1$-Norm Minimization
• Immiscible Color Flows in Optimal Transport Networks for Image Classification

Cited by in corpus (2)

• Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
• Primal Methods for Variational Inequality Problems with Functional Constraints