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

• 成果类型: Article
• 署名作者: Haasler, Isabel; Ringh, Axel; Chen, Yongxin; Karlsson, Johan
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Chalmers University of Technology; University of Gothenburg; University System of Georgia; Georgia Institute of Technology; Royal Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0148
• 发表日期: 2024
• 页码: 986-1011
• 关键词: model-predictive control; real-time optimization; search filter methods; exponential decay; STABILITY; DECOMPOSITION; sensitivity

摘要

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 entropyregularized 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.