| 1. |
- Haasler, Isabel, et al.
(författare)
-
Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
- 2024
-
Ingår i: Mathematics of Operations Research. - 0364-765X .- 1526-5471. ; 49:2, s. 986-1011
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we develop a new framework for dynamic network flow pro-blems 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 asso-ciated 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.
|
|
| 2. |
- Haasler, Isabel, et al.
(författare)
-
Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
- 2024
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 49:2, s. 986-1011
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 3. |
- Ringh, Axel, et al.
(författare)
-
Graph-structured tensor optimization for nonlinear density control and mean field games
- 2024
-
Ingår i: SIAM Journal of Control and Optimization. - : Society for Industrial & Applied Mathematics (SIAM). - 0363-0129 .- 1095-7138. ; 62:4, s. 2176-2202
-
Tidskriftsartikel (refereegranskat)abstract
- In this work we develop a numerical method for solving a type of convex graph- structured tensor optimization problem. This type of problem, which can be seen as a generalization of multimarginal optimal transport problems with graph-structured costs, appears in many applications. Examples are unbalanced optimal transport and multispecies potential mean field games, where the latter is a class of nonlinear density control problems. The method we develop is based on coordinate ascent in a Lagrangian dual, and under mild assumptions we prove that the algorithm converges globally. Moreover, under a set of stricter assumptions, the algorithm converges R-linearly. To perform the coordinate ascent steps one has to compute projections of the tensor, and doing so by brute force is in general not computationally feasible. Nevertheless, for certain graph structures it is possible to derive efficient methods for computing these projections, and here we specifically consider the graph structure that occurs in multispecies potential mean field games. We also illustrate the methodology on a numerical example from this problem class.
|
|
