A metaheuristic for a numerical approximation to the mass transfer problem

• Autorzy: Avendaño-Garrido M. L. , Gabriel-Argüelles J. R. , Quintana-Torres L. , Mezura-Montes E.

Identyfikatory

DOI

10.1515/amcs-2016-0053

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Monge–Kantorovich mass transfer problem; finite dimensional linear programming; transport problem; metaheuristic algorithm; scatter search

PL

programowanie skończenie wymiarowe; zadanie transportowe; algorytm metaheurystyczny; scatter search

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 4
• Strony: 757--766
• Opis fizyczny: Bibliogr. 24 poz., tab., wykr.

Twórcy

autor

Avendaño-Garrido M. L.

• Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico

autor

Gabriel-Argüelles J. R.

• Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico

autor

Quintana-Torres L.

• Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico

autor

Mezura-Montes E.

• Artificial Intelligence Research Centre, University of Veracruz, Sebastián Camacho 5, Col. Centro, 91000, Xalapa, Veracruz, Mexico

Bibliografia

• [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.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.