Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 26 | 4 | 757-766
Tytuł artykułu

A metaheuristic for a numerical approximation to the mass transfer problem

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico
  • Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico
  • Faculty of Mathematics, University of Veracruz, Circuito Gonzalo Aguirre Beltrán S/N, Zona Universitaria, 91090, Xalapa, Veracruz, Mexico
  • Artificial Intelligence Research Centre, University of Veracruz, Sebastián Camacho 5, Col. Centro, 91000, Xalapa, Veracruz, Mexico
  • Anderson, E. and Nash, P. (1987). Linear Programming in Infinite-dimensional Spaces, Wiley, New York, NY.
  • 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.
  • Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2010). Linear Programming and Network Flows, Wiley-Interscience, Hoboken, NJ.
  • Benamou, J. (2003). Numerical resolution of an unbalanced mass transport problem, ESAIM Mathematical Modelling and Numerical Analysis 37(5): 851-868.
  • Benamou, J. and Brenier, Y. (2000). A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numerische Mathematik 84(3): 375-393.
  • Bosc, D. (2010). Numerical approximation of optimal transport maps, SSRN Electronic Journal, DOI: 10.2139/ssrn.1730684.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Hernández-Lerma, O. and Lasserre, J. (1998). Approximation schemes for infinite linear programs, SIAM Journal on Optimization 8(4): 973-988.
  • Kantorovich, L. (2006a). On a problem of Monge, Journal of Mathematical Sciences 133(4): 225-226.
  • Kantorovich, L. (2006b). On the translocation of masses, Journal of Mathematical Sciences 133(4): 1381-1382.
  • 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.
  • Levin, V. (2006). Optimality conditions and exact solutions to the two-dimensional Monge-Kantorovich problem, Journal of Mathematical Sciences 133(4): 1456-1463.
  • Martí, R., Laguna, M. and Glover, F. (2006). Principles of scatter search, European Journal of Operational Research 169(2): 359-372.
  • Mèrigot, Q. (2011). A multiscale approach to optimal transport, Computer Graphics Forum 30(5): 1583-1592.
  • Monge, G. (1781). Mémoire sur la théorie des déblais et des remblais, De l'Imprimerie Royale, Paris.
  • Rachev, S. (1991). Probability Metrics and the Stability of Stochastic Models, Wiley, New York, NY.
  • Rachev, S. and Rüschendorf, L. (1998). Mass Transportation Problems, Vol. I, Springer, New York, NY.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.