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

References

• [1] Altschuler JM, Boix-Adsera E (2023) Polynomial-time algorithms for multimarginal optimal transport problems with structure. Math. Programming 199(1–2):1107–1178.Crossref, Google Scholar
• [2] Aronson J (1989) A survey of dynamic network flows. Ann. Oper. Res. 20(1):1–66.Crossref, Google Scholar
• [3] Bacon X (2020) Multi-species optimal transportation. J. Optim. Theory Appl. 184(2):315–337.Crossref, Google Scholar
• [4] Barnhart C, Krishnan N, Vance PH, Floudas C, Pardalos P (2009) Multicommodity flow problems. Floudas CA, Pardalos PM, eds. Encyclopedia of Optimization (Springer, New York), 2354–2362.Google Scholar
• [5] Bauschke H, Lewis A (2000) Dykstras algorithm with Bregman projections: A convergence proof. Optimization 48(4):409–427.Crossref, Google Scholar
• [6] Benamou JD, Brenier Y (2000) A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84(3):375–393.Crossref, Google Scholar
• [7] Benamou JD, Brenier Y, Guittet K (2004) Numerical analysis of a multi-phasic mass transport problem. Contemporary Math. 353:1–18.Crossref, Google Scholar
• [8] Benamou JD, Carlier G, Cuturi M, Nenna L, Peyré G (2015) Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37(2):A1111–A1138.Crossref, Google Scholar
• [9] Bertsekas DP, Tseng P (1988) Relaxation methods for minimum cost ordinary and generalized network flow problems. Oper. Res. 36(1):93–114.Link, Google Scholar
• [10] Bertsimas D, Patterson SS (2000) The traffic flow management rerouting problem in air traffic control: A dynamic network flow approach. Transportation Sci. 34(3):239–255.Link, Google Scholar
• [11] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [12] Brockett RW (2012) Notes on the control of the Liouville equation. Cannarsa P, Coron J-M, eds. Control of Partial Differential Equations, Chapter 2 (Springer, Berlin), 101–129.Crossref, Google Scholar
• [13] Carlino D, Depinet M, Khandelwal P, Stone P (2012) Approximately orchestrated routing and transportation analyzer: Large-scale traffic simulation for autonomous vehicles. 2012 15th Internat. IEEE Conf. Intelligent Transportation Systems (IEEE, Piscataway, NJ), 334–339.Google Scholar
• [14] Chen Y, Georgiou TT, Pavon M (2016) On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint. J. Optim. Theory Appl. 169(2):671–691.Crossref, Google Scholar
• [15] Chen Y, Georgiou TT, Pavon M (2016) Optimal steering of a linear stochastic system to a final probability distribution. Part I. IEEE Trans. Automatic Control 61(5):1158–1169.Crossref, Google Scholar
• [16] Chen Y, Georgiou TT, Tannenbaum A (2018) Vector-valued optimal mass transport. SIAM J. Appl. Math. 78(3):1682–1696.Crossref, Google Scholar
• [17] Chen Y, Georgiou TT, Pavon M, Tannenbaum A (2016) Robust transport over networks. IEEE Trans. Automatic Control 62(9):4675–4682.Crossref, Google Scholar
• [18] Chen Y, Georgiou TT, Pavon M, Tannenbaum A (2017) Efficient robust routing for single commodity network flows. IEEE Trans. Automatic Control 63(7):2287–2294.Crossref, Google Scholar
• [19] Chen Y, Georgiou TT, Pavon M, Tannenbaum A (2019) Relaxed Schrödinger bridges and robust network routing. IEEE Trans. Control Network Systems 7(2):923–931.Crossref, Google Scholar
• [20] Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Adv. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 2292–2300.Google Scholar
• [21] Diestel R (2017) Graph Theory (Springer, Berlin).Crossref, Google Scholar
• [22] Dvurechensky P, Gasnikov A, Kroshnin A (2018) Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm. Internat. Conf. Machine Learn. (PMLR, New York), 1367–1376.Google Scholar
• [23] Elvander F, Haasler I, Jakobsson A, Karlsson J (2020) Multi-marginal optimal mass transport using partial information with applications in robust localization and sensor fusion. Signal Processing 171:107474.Crossref, Google Scholar
• [24] Farvolden JM, Powell WB, Lustig IJ (1993) A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem. Oper. Res. 41(4):669–693.Link, Google Scholar
• [25] Ford LR, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Management Sci. 5(1):97–101.Link, Google Scholar
• [26] Ford LR, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Oper. Res. 6(3):419–433.Link, Google Scholar
• [27] Ford LR, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [28] Gangbo W, Świech A (1998) Optimal maps for the multidimensional Monge-Kantorovich problem. Comm. Pure Appl. Math. Courant Inst. Math. Sci. 51(1):23–45.Crossref, Google Scholar
• [29] Gendron B, Crainic TG, Frangioni A (1999) Multicommodity capacitated network design. Sansò B, Soriano P, eds. Telecommunications Network Planning, Chapter 1 (Springer, New York), 1–19.Crossref, Google Scholar
• [30] Gurobi Optimization LLC (2022) Gurobi optimizer reference manual. Accessed June 5, 2023, https://www.gurobi.com.Google Scholar
• [31] Haasler I, Chen Y, Karlsson J (2020) Optimal steering of ensembles with origin-destination constraints. IEEE Control Systems Lett. 5(3):881–886.Crossref, Google Scholar
• [32] Haasler I, Ringh A, Chen Y, Karlsson J (2019) Estimating ensemble flows on a hidden Markov chain. 2019 IEEE 58th Conf. Decision Control (CDC) (IEEE, Piscataway, NJ), 1331–1338.Google Scholar
• [33] Haasler I, Ringh A, Chen Y, Karlsson J (2021) Multi-marginal optimal transport with a tree-structured cost and the Schrödinger bridge problem. SIAM J. Control Optim. 59(4):2428–2453.Crossref, Google Scholar
• [34] Haasler I, Singh R, Zhang Q, Karlsson J, Chen Y (2021) Multi-marginal optimal transport and probabilistic graphical models. IEEE Trans. Inform. Theory 67(7):4647–4668.Crossref, Google Scholar
• [35] Haghani A, Oh SC (1996) Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations. Transportation Res. Part A Policy Pract. 30(3):231–250.Crossref, Google Scholar
• [36] Hall A, Hippler S, Skutella M (2007) Multicommodity flows over time: Efficient algorithms and complexity. Theoret. Comput. Sci. 379(3):387–404.Crossref, Google Scholar
• [37] IBM ILOG CPLEX (2019) Optimization Studio 12.10.0: CP optimizer online documentation. Acccessed June 5, 2023, https://www.ibm.com/docs/en/icos/12.10.0.Google Scholar
• [38] Jones K, Lustig I, Farvolden J, Powell W (1993) Multicommodity network flows: The impact of formulation on decomposition. Math. Programming 62(1–3):95–117.Crossref, Google Scholar
• [39] Karlsson J, Ringh A (2017) Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport. SIAM J. Imaging Sci. 10(4):1935–1962.Crossref, Google Scholar
• [40] Kennington J, Shalaby M (1977) An effective subgradient procedure for minimal cost multicommodity flow problems. Management Sci. 23(9):994–1004.Link, Google Scholar
• [41] Kennington JL (1978) A survey of linear cost multicommodity network flows. Oper. Res. 26(2):209–236.Link, Google Scholar
• [42] Khodayifar S (2021) Minimum cost multicommodity network flow problem in time-varying networks: By decomposition principle. Optim. Lett. 15(2):1009–1026.Crossref, Google Scholar
• [43] Léonard C (2014) A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Continuous Dynamical Systems 34(4):1533–1574.Crossref, Google Scholar
• [44] Levinson J, Askeland J, Becker J, Dolson J, Held D, Kammel S, Kolter J, et al. (2011) Toward fully autonomous driving: Systems and algorithms. 2011 IEEE Intelligent Vehicles Sympos. (IV) (IEEE, Piscataway, NJ), 163–168.Google Scholar
• [45] Lin T, Ho N, Cuturi M, Jordan MI (2022) On the complexity of approximating multimarginal optimal transport. J. Machine Learn. Res. 23(65):1–43.Google Scholar
• [46] Lin T, Ho N, Chen X, Cuturi M, Jordan M (2020) Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 5368–5380.Google Scholar
• [47] Luo ZQ, Tseng P (1992) On the convergence of the coordinate descent method for convex differentiable minimization. J. Optim. Theory Appl. 72(1):7–35.Crossref, Google Scholar
• [48] McBride R (1998) Progress made in solving the multicommodity flow problem. SIAM J. Optim. 8(4):947–955.Crossref, Google Scholar
• [49] Nenna L (2016) Numerical methods for multi-marginal optimal transportation. PhD thesis, PSL, Paris.Google Scholar
• [50] Pasquale C, Sacone S, Siri S, Ferrara A (2019) Traffic control for freeway networks with sustainability-related objectives: Review and future challenges. Annual Rev. Control 48:312–324.Crossref, Google Scholar
• [51] Pass B (2015) Multi-marginal optimal transport: Theory and applications. ESAIM Math. Model. Numer. Anal. 49(6):1771–1790.Crossref, Google Scholar
• [52] Pavon M, Ticozzi F (2010) Discrete-time classical and quantum Markovian evolutions: Maximum entropy problems on path space. J. Math. Phys. 51(4):042104.Crossref, Google Scholar
• [53] Peyré G, Cuturi M (2019) Computational optimal transport: With applications to data science. Foundations Trends Machine Learn. 11(5–6):355–607.Crossref, Google Scholar
• [54] Retvdri G, Bíró J, Cinkler T (2004) A novel Lagrangian-relaxation to the minimum cost multicommodity flow problem and its application to ospf traffic engineering. Proc. ISCC 2004. Ninth Internat. Sympos. Comput. Comm., vol. 2 (IEEE, Piscataway, NJ), 957–962.Google Scholar
• [55] Rüschendorf L (1995) Optimal solutions of multivariate coupling problems. Appl. Math. 23(3):325–338.Google Scholar
• [56] Rüschendorf L, Uckelmann L (2002) On the n-coupling problem. J. Multivariate Anal. 81(2):242–258.Crossref, Google Scholar
• [57] Tomlin JA (1966) Minimum-cost multicommodity network flows. Oper. Res. 14(1):45–51.Link, Google Scholar
• [58] Tseng P (1990) Dual ascent methods for problems with strictly convex costs and linear constraints: A unified approach. SIAM J. Control Optim. 28(1):214–242.Crossref, Google Scholar
• [59] Villani C (2008) Optimal Transport: Old and New (Springer, Berlin).Google Scholar
• [60] Wang IL (2018) Multicommodity network flows: A survey. Part I. Applications and formulations. Internat. J. Oper. Res. 15(4):145–153.Google Scholar
• [61] Yamada T (1996) A network flow approach to a city emergency evacuation planning. Internat. J. Systems Sci. 27(10):931–936.Crossref, Google Scholar