Geodesic
A metaheuristic for a numerical approximation to the mass transfer problem
International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 4, pp. 757-766.

Voir la notice de l'article provenant de la source Library of Science

This work presents an improvement of the approximation scheme for the Monge–Kantorovich (MK) mass transfer problem on compact spaces, which is studied by Gabriel et al. (2010), whose scheme discretizes the MK problem, reduced to solve a sequence of finite transport problems. The improvement presented in this work uses a metaheuristic algorithm inspired by scatter search in order to reduce the dimensionality of each transport problem. The new scheme solves a sequence of linear programming problems similar to the transport ones but with a lower dimension. The proposed metaheuristic is supported by a convergence theorem. Finally, examples with an exact solution are used to illustrate the performance of our proposal.
Keywords: Monge–Kantorovich mass transfer problem, finite dimensional linear programming, transport problem, metaheuristic algorithm, scatter search
Mots-clés : programowanie skończenie wymiarowe, zadanie transportowe, algorytm metaheurystyczny, scatter search 
@article{IJAMCS_2016_26_4_a2,
     author = {Avenda\~no-Garrido, M. L. and Gabriel-Arg\"uelles, J. R. and Quintana-Torres, L. and Mezura-Montes, E.},
     title = {A metaheuristic for a numerical approximation to the mass transfer problem},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {757--766},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_4_a2/}
}
TY  - JOUR
AU  - Avendaño-Garrido, M. L.
AU  - Gabriel-Argüelles, J. R.
AU  - Quintana-Torres, L.
AU  - Mezura-Montes, E.
TI  - A metaheuristic for a numerical approximation to the mass transfer problem
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2016
SP  - 757
EP  - 766
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_4_a2/
LA  - en
ID  - IJAMCS_2016_26_4_a2
ER  - 
%0 Journal Article
%A Avendaño-Garrido, M. L.
%A Gabriel-Argüelles, J. R.
%A Quintana-Torres, L.
%A Mezura-Montes, E.
%T A metaheuristic for a numerical approximation to the mass transfer problem
%J International Journal of Applied Mathematics and Computer Science
%D 2016
%P 757-766
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_4_a2/
%G en
%F IJAMCS_2016_26_4_a2
Avendaño-Garrido, M. L.; Gabriel-Argüelles, J. R.; Quintana-Torres, L.; Mezura-Montes, E. A metaheuristic for a numerical approximation to the mass transfer problem. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) no. 4, pp. 757-766. http://geodesic.mathdoc.fr/item/IJAMCS_2016_26_4_a2/

[1] Anderson, E. and Nash, P. (1987). Linear Programming in Infinite-dimensional Spaces, Wiley, New York, NY.

[2] Anderson, E. and Philpott, A. (1984). Duality and an algorithm for a class of continuous transportation problems, Mathematics of Operations Research 9(2): 222–231.

[3] Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2010). Linear Programming and Network Flows,Wiley-Interscience, Hoboken, NJ.

[4] Benamou, J. (2003). Numerical resolution of an unbalanced mass transport problem, ESAIM Mathematical Modelling and Numerical Analysis 37(5): 851–868.

[5] Benamou, J. and Brenier, Y. (2000). A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem, Numerische Mathematik 84(3): 375–393.

[6] Bosc, D. (2010). Numerical approximation of optimal transport maps, SSRN Electronic Journal, DOI: 10.2139/ssrn.1730684.

[7] Caffarelli, L., Feldman, M. and McCann, R. (2002). Constructing optimal maps for Monge’s transport problem as a limit of strictly convex costs, Journal of the American Mathematical Society 15(1): 1–26.

[8] Gabriel, J., González-Hernández, J. and López-Martínez, R. (2010). Numerical approximations to the mass transfer problem on compact spaces, IMA Journal of Numerical Analysis 30(4): 1121–1136.

[9] Glover, F. (1998). A template for scatter search and path relinking, in J.-K. Hao et al. (Eds.), Artificial Evolution, Lecture Notes in Computer Science, Vol. 1363, Springer, Berlin/Heidelberg, pp. 1–51.

[10] González-Hernández, J., Gabriel, J. and Hernández-Lerma, O. (2006). On solutions to the mass transfer problem, SIAM Journal on Optimization 17(2): 485–499.

[11] Guittet, K. (2003). On the time-continuous mass transport problem and its approximation by augmented Lagrangian techniques, SIAM Journal on Numerical Analysis 41(1): 382–399.

[12] Haker, S., Zhu, L., Tannenbaum, A. and Angenent, S. (2004). Optimal mass transport for registration and warping, International Journal of Computer Vision 63(3): 225–240.

[13] Hanin, L., Rachev, S. and Yakovlev, A. (1993). On the optimal control of cancer radiotherapy for non-homogeneous cell population, Advances in Applied Probability 25(1): 1–23.

[14] Hernández-Lerma, O. and Gabriel, J. (2002). Strong duality of the Monge–Kantorovich mass transfer problem in metric spaces, Mathematische Zeitschrift 239(3): 579–591.

[15] Hernández-Lerma, O. and Lasserre, J. (1998). Approximation schemes for infinite linear programs, SIAM Journal on Optimization 8(4): 973–988.

[16] Kantorovich, L. (2006a). On a problem of Monge, Journal of Mathematical Sciences 133(4): 225–226.

[17] Kantorovich, L. (2006b). On the translocation of masses, Journal of Mathematical Sciences 133(4): 1381–1382.

[18] Laguna, M., Gortázar, F., Gallego, M., Duarte, A. and Martí, R. (2014). A black-box scatter search for optimization problems with integer variables, Journal of Global Optimization 58(3): 497–516.

[19] Levin, V. (2006). Optimality conditions and exact solutions to the two-dimensional Monge–Kantorovich problem, Journal of Mathematical Sciences 133(4): 1456–1463.

[20] Martí, R., Laguna, M. and Glover, F. (2006). Principles of scatter search, European Journal of Operational Research 169(2): 359–372.

[21] Mèrigot, Q. (2011). A multiscale approach to optimal transport, Computer Graphics Forum 30(5): 1583–1592.

[22] Monge, G. (1781). Mémoire sur la théorie des déblais et des remblais, De l’Imprimerie Royale, Paris.

[23] Rachev, S. (1991). Probability Metrics and the Stability of Stochastic Models, Wiley, New York, NY.

[24] Rachev, S. and Rüschendorf, L. (1998). Mass Transportation Problems, Vol. I, Springer, New York, NY.