EUVIMEDEUVIMED entdecken
Crossref

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

Isabel Haasler, Axel Ringh, Yongxin Chen, Johan Karlsson

Mathematics of Operations Research · 2024-05 · 49 (2) · 986-1011

DOI: 10.1287/moor.2021.0148 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2024-05. Verfasst von Isabel Haasler und 3 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 52 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. Funding: This work was supported by KTH Digital Futures, Knut och Alice Wallenbergs Stiftelse [Grants KAW 2018.0349, KAW 2021.0274, the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation], Vetenskapsrådet [Grant 2020-03454], and the National Science Foundation [Grants 1942523 and 2206576].

Zitieren

APA

Haasler, I., Ringh, A., Chen, Y., & Karlsson, J. (2024). Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport. Mathematics of Operations Research, 49(2), 986-1011. https://doi.org/10.1287/moor.2021.0148

Vancouver

Haasler I, Ringh A, Chen Y, Karlsson J. Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport. Mathematics of Operations Research. 2024;49(2):986-1011. doi:10.1287/moor.2021.0148

BibTeX
@article{Haasler2024,
  author = {Haasler, Isabel and Ringh, Axel and Chen, Yongxin and Karlsson, Johan},
  title = {Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport},
  journal = {Mathematics of Operations Research},
  year = {2024},
  volume = {49},
  number = {2},
  pages = {986--1011},
  doi = {10.1287/moor.2021.0148}
}
Kostenlos starten →