An Interior Point–Inspired Algorithm for Linear Programs Arising in Discrete Optimal Transport

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• Aurenhammer F, Hoffmann F, Aronov B (1998) Minkowski-type theorems and least-squares clustering. Algorithmica 20(1):61–76.Crossref, Google Scholar
• Bergamaschi L, Gondzio J, Venturin M, Zilli G (2007) Inexact constraint preconditioners for linear systems arising in interior point methods. Comput. Optim. Appl. 36(2):137–147.Crossref, Google Scholar
• Bertsekas D (1998) Network Optimization: Continuous and Discrete Models (Athena Scientific, Nashua, NH).Google Scholar
• Bocanegra S, Campos F, Oliveira A (2007) Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods. Comput. Optim. Appl. 36(2):149–164.Crossref, Google Scholar
• Castro J (2000) A specialized interior-point algorithm for multicommodity network flows. SIAM J. Optim. 10(3):852–877.Crossref, Google Scholar
• Castro J, Cuesta J (2011) Quadratic regularizations in an interior point method for primal block-angular problems. Math. Programming 130(2):415–445.Crossref, Google Scholar
• Castro J, Nasini S (2021) A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks. Eur. J. Oper. Res. 290(3):857–869.Crossref, Google Scholar
• Chai JS, Toh KC (2007) Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming. Comput. Optim. Appl. 36(2):221–247.Crossref, Google Scholar
• Colombo M, Gondzio J (2008) Further development of multiple centrality correctors for interior point methods. Comput. Optim. Appl. 41(3):277–305.Crossref, Google Scholar
• CPLEX (2019) IBM ILOG CPLEX, version 20.1. Accessed May 1, 2022, https://www.ibm.com/analytics/cplex-optimizer.Google Scholar
• Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Proc. 26th Internat. Conf. Neural Information Processing Systems (Curran Associates Inc., Red Hook, NH), 2292–2300.Google Scholar
• De Simone V, Di Serafino D, Gondzio J, Pougkakiotis S, Viola M (2022) Sparse approximations with interior point methods. SIAM Rev. 64(4):954–988.Crossref, Google Scholar
• El-Bakry AS, Tapia RA, Zhang Y (1994) A study of indicators for identifying zero variables in interior-point methods. SIAM Rev. 36(1):45–72.Crossref, Google Scholar
• Eötvös Loránd University (2014) LEMON, version 1.3.1. Accessed October 1, 2022, https://lemon.cs.elte.hu/trac/lemon.Google Scholar
• Facca E, Benzi M (2021) Fast iterative solution of the optimal transport problem on graphs. SIAM J. Sci. Comput. 43(3):A2295–A2319.Crossref, Google Scholar
• Fountoulakis K, Gondzio J, Zhlobich P (2014) Matrix-free interior point method for compressed sensing problems. Math. Programming Comput. 6(1):1–31.Crossref, Google Scholar
• Frangioni A, Gentile C (2004) New preconditioners for KKT systems of network flow problems. SIAM J. Optim. 14(3):894–913.Crossref, Google Scholar
• Ghidini CTLS, Oliveira ARL, Silva J, Velazco MI (2012) Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods. Linear Algebra Appl. 436(5):1267–1284.Crossref, Google Scholar
• Golub GH, Van Loan CF (1996) Matrix Computations (The Johns Hopkins University Press, Baltimore).Google Scholar
• Gondzio J (1998) Warm start of the primal-dual method applied in the cutting plane scheme. Math. Programming 83(1):125–143.Crossref, Google Scholar
• Gondzio J (2012) Matrix-free interior point method. Comput. Optim. Appl. 51(2):457–480.Crossref, Google Scholar
• Gondzio J, Gonzalez-Brevis P, Munari P (2013) New developments in the primal–dual column generation technique. Eur. J. Oper. Res. 224(1):41–51.Crossref, Google Scholar
• Gondzio J, Lassas M, Latva-Aijo SM, Siltanen S, Zanetti F (2022) Material-separating regularizer for multi-energy x-ray tomography. Inverse Problems. 38(2):025013.Crossref, 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
• Hestenes MR, Stiefel E (1952) Methods of conjugate gradients for solving linear systems. J. Res. NIST 49(6):409–436.Google Scholar
• Horn R, Johnson C (1990) Matrix Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Kantorovich L (1958) On the translocation of masses. Management Sci. 5:1–4.Link, Google Scholar
• Kennington JL, Helgason RV (1980) Algorithms for Network Programming (John Wiley and Sons, New York).Google Scholar
• Kovacs P (2015) Minimum-cost flow algorithms: An experimental evaluation. Optim. Methods Software 30(1):94–127.Crossref, Google Scholar
• Ling H, Okada K (2007) An efficient earth mover’s distance algorithm for robust histogram comparison. IEEE Trans. Pattern Anal. Machine Intelligence 29(5):840–853.Crossref, Google Scholar
• Lubbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Merigot Q (2011) A multiscale approach to optimal transport. Comput. Graphics Forum 30(5):1583–1592.Crossref, Google Scholar
• Natale A, Todeschi G (2021) Computation of optimal transport with finite volumes. ESAIM: Mathematical Modelling and Numerical Analysis 55(5):1847–1871.Crossref, Google Scholar
• Oliveira ARL, Sorensen DC (2005) A new class of preconditioners for large-scale linear systems from interior point methods for linear programming. Linear Algebra Appl. 394:1–24.Crossref, Google Scholar
• Orlin J (1996) A polynomial time primal network simplex algorithm for minimum cost flows. Math. Programming 78(2):109–129.Crossref, Google Scholar
• Peyre G, Cuturi M (2019) Computational optimal transport: With applications to data science. Foundations Trends Machine Learn. 11(5-6):355–607.Crossref, Google Scholar
• Resende MG, Veiga G (1993) An implementation of the dual affine scaling algorithm for minimum-cost flow on bipartite uncapacitated networks. SIAM J. Optim. 3(3):516–537.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 (2017) DOTmark: A benchmark for discrete optimal transport. IEEE Access 5:271–282.Crossref, Google Scholar
• Vandenberghe L, Andersen M (2014) Chordal graphs and semidefinite optimization. Foundations Trends Optim. 1(4):241–433.Crossref, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers J, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 331–358.Crossref, Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. Junger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008 (Springer, Berlin), 431–502.Crossref, Google Scholar
• Velazco MI, Oliveira ARL, Campos FF (2010) A note on hybrid preconditioners for large-scale normal equations arising from interior-point methods. Optim. Methods Software 25(2):321–332.Crossref, Google Scholar
• Wijesinghe J, Chen P (2022) Matrix balancing based interior point methods for point set matching problems. Preprint, submitted December 24, https://arxiv.org/abs/2202.09763v3.Google Scholar
• Wright SJ (1997) Primal-Dual Interior-Point Methods (SIAM, Philadelphia).Crossref, Google Scholar
• Zanetti F, Gondzio J (2023a) An interior-point-inspired algorithm for linear programs arising in discrete optimal transport. http://dx.doi.org/10.1287/ijoc.2022.0184.cd, https://github.com/INFORMSJoC/2022.0184.Google Scholar
• Zanetti F, Gondzio J (2023b) A new stopping criterion for Krylov solvers applied in interior point methods. SIAM J. Sci. Comput. Forthcoming.Crossref, Google Scholar