Iterated Inside Out: A New Exact Algorithm for the Transportation Problem

References

• Armstrong RD, Jin Z (1997) A new strongly polynomial dual network simplex algorithm. Math. Programming 78(2):131–148.Crossref, Google Scholar
• Bargetto R, Della Croce F, Scatamacchia R (2025) Iterated inside out: A new exact algorithm for the transportation problem. https://doi.org/10.1287/ijoc.2024.0642.cd, https://github.com/INFORMSJoC/2024.0642.Google Scholar
• Bassetti F, Gualandi S, Veneroni M (2020) On the computation of Kantorovich–Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows. SIAM J. Optim. 30(3):2441–2469.Crossref, Google Scholar
• Bonneel N, van de Panne M, Paris S, Heidrich W (2011) Displacement interpolation using Lagrangian mass transport. ACM Trans. Graphics 30(6):1–12.Crossref, Google Scholar
• Bulut H (2017) Multiloop transportation simplex algorithm. Optim. Methods Software 32(6):1206–1217.Crossref, Google Scholar
• Cipolla S, Gondzio J, Zanetti F (2024) A regularized interior point method for sparse optimal transport on graphs. Eur. J. Oper. Res. 319(2):413–426.Crossref, Google Scholar
• Cunningham WH (1976) A network simplex method. Math. Programming 11(1):105–116.Crossref, Google Scholar
• Dantzig GB (1951) Application of the simplex method to a transportation problem. Koopmans TC, ed. Activity Analysis of Production and Allocation (John Wiley, New York), 359–373.Google Scholar
• Ford LR, Fulkerson DR (1956) Solving the transportation problem. Management Sci. 3(1):24–32.Link, Google Scholar
• Gottschlich C, Schuhmacher D (2014) The shortlist method for fast computation of the earth mover’s distance and finding optimal solutions to transportation problems. PLoS One 9(10):e110214.Crossref, Google Scholar
• Hitchcock FL (1941) The distribution of a product from several sources to numerous localities. J. Math. Phys. 20:224–230.Crossref, Google Scholar
• Kantorovich LV (1942) On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.) 37:199–201.Google Scholar
• Kovács P (2015) Minimum-cost flow algorithms: An experimental evaluation. Optim. Methods Software 30(1):94–127.Crossref, Google Scholar
• LEMON (2010) Library for efficient modeling and optimization in networks. Accessed January 31, 2024, http://lemon.cs.elte.hu/trac/lemon.Google Scholar
• Luenberger DG, Ye Y (2008) Linear and Nonlinear Programming. International Series in Operations Research & Management Science, vol. 116 (Springer, New York).Crossref, Google Scholar
• Monge G (1781) Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris (Imprimerie Royale, Paris), 666–704.Google Scholar
• Orlin JB (1996) A polynomial time primal network simplex algorithm for minimum cost flows. Math. Programming 78(2):109–129.Crossref, Google Scholar
• Schmitzer B (2016) A sparse multiscale algorithm for dense optimal transport. J. Math. Imaging Vision 56(2):238–259.Crossref, Google Scholar
• Schrieber J, Schuhmacher D, Gottschlich C (2016) DOTmark—A benchmark for discrete optimal transport. IEEE Access 5:271–282.Crossref, Google Scholar
• Schwinn J, Werner R (2019) On the effectiveness of primal and dual heuristics for the transportation problem. IMA J. Management Math. 30(3):281–303.Crossref, Google Scholar
• Zanetti F, Gondzio J (2023) An interior point-inspired algorithm for linear programs arising in discrete optimal transport. INFORMS J. Comput. 35(5):1061–1078.Link, Google Scholar