  In this work, the authors address the Optimal Transport (OT) problem on
graphs using a proximal stabilized Interior Point Method (IPM). In particular,
strongly leveraging on the induced primal-dual regularization, the authors
propose to solve large scale OT problems on sparse graphs using a bespoke IPM
algorithm able to suitably exploit primal-dual regularization in order to
enforce scalability. Indeed, the authors prove that the introduction of the
regularization allows to use sparsified versions of the normal Newton equations
to inexpensively generate IPM search directions. A detailed theoretical
analysis is carried out showing the polynomial convergence of the inner
algorithm in the proposed computational framework. Moreover, the presented
numerical results showcase the efficiency and robustness of the proposed
approach when compared to network simplex solvers.
