Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach (Journal of Computational Mathematics, 2021)
We compute and visualize solutions to the Optimal Transportation (OT) problem fora wide class of cost functions. The standard linear programming (LP) discretization ofthe continuous problem becomes intractable for moderate grid sizes. A grid refinementmethod results in a linear cost algorithm. Weak convergence of solutions is established andbarycentric projection of transference plans is used to improve the accuracy of solutions.Optimal maps between nonconvex domains, partial OT free boundaries, and high accuracybarycenters are presented.
Keywords: Optimal Transportation; Linear Programming; Monge-Kantorovich; Barycenter.