Numerical solutions of the mass transfer problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1, p. 1-17
Let $\mu$ and $\nu$ be two probability measures on the real line and let $c$ be a lower semicontinuous function on the plane. The mass transfer problem consists in determining a measure $\xi$ whose marginals coincide with $\mu$ and $\nu$, and whose total cost $\phantom{\rule{0.277778em}{0ex}}\int \int \phantom{\rule{0.277778em}{0ex}}\phantom{\rule{0.166667em}{0ex}}\phantom{\rule{0.166667em}{0ex}}c\left(x,y\right)\phantom{\rule{0.166667em}{0ex}}\mathrm{d}\xi \left(x,y\right)$ is minimum. In this paper we present three algorithms to solve numerically this Monge-Kantorovitch problem when the commodity being shipped is one-dimensional and not necessarily confined to a bounded interval. We illustrate these numerical methods and determine the convergence rate.
@article{RO_2006__40_1_1_0,
author = {Dubuc, Serge and Kagabo, Issa},
title = {Numerical solutions of the mass transfer problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
pages = {1-17},
doi = {10.1051/ro:2006011},
zbl = {pre05140663},
mrnumber = {2248419},
language = {en},
url = {http://www.numdam.org/item/RO_2006__40_1_1_0}
}

Dubuc, Serge; Kagabo, Issa. Numerical solutions of the mass transfer problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 1, pp. 1-17. doi : 10.1051/ro:2006011. http://www.numdam.org/item/RO_2006__40_1_1_0/

[1] M. Abramowitz and I.A. Stegun, Handbook of Mathematical Functions With Formulas, Graphs, and Mathematical Tables. Washington, D.C. (1964). | Zbl 0171.38503

[2] E.J. Anderson and A.B. Philpott, Duality and an algorithm for a class of continuous transportation problems. Math. Oper. Res. 9 (1984) 222-231. | Zbl 0538.90057

[3] E.J. Anderson and P. Nash, Linear Programming in Infinite-Dimensional Spaces. Theory and Application. John Wiley & Sons, Chichester (1987). | MR 893179 | Zbl 0632.90038

[4] P.E. Appell, Mémoire sur les déblais et les remblais des systèmes continus ou discontinus 181-208. | JFM 20.0375.01

[5] P.E. Appell, Le problème géométrique des déblais et remblais. Gauthier-Villars, Paris (1928). | JFM 54.0527.03 | Numdam

[6] S. Dubuc and M. Tanguay, Déplacement de matériel continu unidimensionnel à moindre coût. RAIRO Rech. Oper., 20 (1986) 139-161. | Numdam | Zbl 0601.90104

[7] M. Fréchet, Sur les tableaux de corrélation dont les marges sont données. Ann. Univ. Lyon 14 (1951) 53-77. | Zbl 0045.22905

[8] M.D. Grigoriadis, An efficient implementation of the network simplex method. Netflow in Pisa (Pisa, 1983). Math. Program. Stud. 26 (1986) 83-111. | Zbl 0594.90025

[9] F.L. Hitchcock, The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941) 224-230. | JFM 67.0528.04

[10] W. Hoeffding, Masstabinvariante Korrelations-theorie. Schr. Math. Inst. Univ. Berlin 5 (1940) 181-233. | JFM 66.0649.02

[11] L. Kantorovitch, On the translocation of masses. Doklady Akad. Nauk. SSSR 37 (1942) 199-201. | Zbl 0061.09705

[12] H.G. Kellerer, Duality theorems for marginal problems. Z. Wahrsch. Verw. Gebiete 67 (1984) 399-432. | Zbl 0535.60002

[13] V.L. Levin and A.A. Milyutin, The Problem of Mass Transfer with a Discontinuous Cost Function and the Mass Statement of the Duality for Convex Extremal Problems. Uspehi Mat. Nauk. 34 (1979) 3-68. | Zbl 0437.46064

[14] G. Monge, Mémoire sur la théorie des déblais et des remblais. Mém. Math. Phys. Acad. Royale Sci., Paris (1781) 666-704.

[15] S.T. Rachev and L. Rüschendorf, Solution of some transportation problems with relaxed or additional constraints SIAM J. Control Optim. 32 (1994), 673-689. | Zbl 0797.60019

[16] A.H. Tchen, Inequalities for distributions with given marginals Ann. Prob. 8 (1980) 814-827. | Zbl 0459.62010