Algorithms for constrained optimal transport

We derive iterative scaling algorithms of the Sinkhorn-Knopp (SK) type for constrained optimal transport. The constraints are in the form of prior-imposed zeroes in the transport plan. Based on classical Bregman arguments, we prove asymptotic convergence of our algorithms to a unique optimal solutio...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-02
Main Authors: Corless, Martin, Quinn, Anthony, Boufelja, Sarah, Shorten, Robert
Format: Article
Language:English
Subjects:
Algorithms
Constraints
Convergence
Electric vehicles
Transportation planning
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We derive iterative scaling algorithms of the Sinkhorn-Knopp (SK) type for constrained optimal transport. The constraints are in the form of prior-imposed zeroes in the transport plan. Based on classical Bregman arguments, we prove asymptotic convergence of our algorithms to a unique optimal solution. New insights obtained from the convergence proof are highlighted. An example from electrical vehicle charging in a smart city context is outlined, in which the prior zero-constraints prevent energy from being transported from some providers to some vehicles.
ISSN:2331-8422