Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport

Isabel Haasler (), Axel Ringh (), Yongxin Chen () and Johan Karlsson ()
Additional contact information
Isabel Haasler: Signal Processing Laboratory 4, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Axel Ringh: Department of Mathematical Sciences, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden; Department of Mathematical Sciences, University of Gothenburg, SE-412 96 Gothenburg, Sweden
Yongxin Chen: School of Aerospace Engineering, Georgia Institute of Technology, GA 30332 Atlanta, Georgia
Johan Karlsson: Department of Mathematics, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden

Mathematics of Operations Research, 2024, vol. 49, issue 2, 986-1011

Abstract: In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy-regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.

Keywords: Primary: 49Q22; 90-08; 90C35; 90C08; 49M29; multimarginal optimal transport; dynamic network flow; multicommodity network flow; Sinkhorn’s method; Computational methods; traffic routing (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0148 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:986-1011

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().