A metaheuristic for a numerical approximation to the mass transfer problem
Martha L. Avendaño-Garrido ; José R. Gabriel-Argũelles ; Ligia Quintana-Torres ; Efrén Mezura-Montes
International Journal of Applied Mathematics and Computer Science, Tome 26 (2016), p. 757-766 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:287182 
@article{bwmeta1.element.bwnjournal-article-amcv26i4p757bwm,
     author = {Martha L. Avenda\~no-Garrido and Jos\'e R. Gabriel-Arg\~uelles and Ligia Quintana-Torres and Efr\'en Mezura-Montes},
     title = {A metaheuristic for a numerical approximation to the mass transfer problem},
     journal = {International Journal of Applied Mathematics and Computer Science},
     volume = {26},
     year = {2016},
     pages = {757-766},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv26i4p757bwm}
}

Martha L. Avendaño-Garrido; José R. Gabriel-Argũelles; Ligia Quintana-Torres; Efrén Mezura-Montes. A metaheuristic for a numerical approximation to the mass transfer problem. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) pp. 757-766. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv26i4p757bwm/

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

[001] 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. | Zbl 0538.90057

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

[003] Benamou, J. (2003). Numerical resolution of an unbalanced mass transport problem, ESAIM Mathematical Modelling and Numerical Analysis 37(5): 851-868. | Zbl 1037.65063

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

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

[006] 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. | Zbl 1053.49032

[007] 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. | Zbl 1210.65109

[008] 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.

[009] 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. | Zbl 1165.49313

[010] 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. | Zbl 1039.65050

[011] 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.

[012] 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. | Zbl 0767.60011

[013] 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. | Zbl 1003.90026

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

[015] Kantorovich, L. (2006a). On a problem of Monge, Journal of Mathematical Sciences 133(4): 225-226. | Zbl 1080.49508

[016] Kantorovich, L. (2006b). On the translocation of masses, Journal of Mathematical Sciences 133(4): 1381-1382. | Zbl 1080.49507

[017] 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. | Zbl 1305.90304

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

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

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

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

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

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