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 (2016)

  • Volume: 26, Issue: 4, page 757-766
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Martha L. Avendaño-Garrido, et al. "A metaheuristic for a numerical approximation to the mass transfer problem." International Journal of Applied Mathematics and Computer Science 26.4 (2016): 757-766. <http://eudml.org/doc/287182>.

@article{MarthaL2016,
abstract = {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.},
author = {Martha L. Avendaño-Garrido, José R. Gabriel-Argũelles, Ligia Quintana-Torres, Efrén Mezura-Montes},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Monge-Kantorovich mass transfer problem; finite dimensional linear programming; transport problem; metaheuristic algorithm; scatter search},
language = {eng},
number = {4},
pages = {757-766},
title = {A metaheuristic for a numerical approximation to the mass transfer problem},
url = {http://eudml.org/doc/287182},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Martha L. Avendaño-Garrido
AU - José R. Gabriel-Argũelles
AU - Ligia Quintana-Torres
AU - Efrén Mezura-Montes
TI - A metaheuristic for a numerical approximation to the mass transfer problem
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 4
SP - 757
EP - 766
AB - 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.
LA - eng
KW - Monge-Kantorovich mass transfer problem; finite dimensional linear programming; transport problem; metaheuristic algorithm; scatter search
UR - http://eudml.org/doc/287182
ER -

References

top
  1. Anderson, E. and Nash, P. (1987). Linear Programming in Infinite-dimensional Spaces, Wiley, New York, NY. Zbl0632.90038
  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. Zbl0538.90057
  3. Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2010). Linear Programming and Network Flows, Wiley-Interscience, Hoboken, NJ. Zbl1200.90002
  4. Benamou, J. (2003). Numerical resolution of an unbalanced mass transport problem, ESAIM Mathematical Modelling and Numerical Analysis 37(5): 851-868. Zbl1037.65063
  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. Zbl0968.76069
  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. Zbl1053.49032
  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. Zbl1210.65109
  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. Zbl1165.49313
  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. Zbl1039.65050
  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. Zbl0767.60011
  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. Zbl1003.90026
  15. Hernández-Lerma, O. and Lasserre, J. (1998). Approximation schemes for infinite linear programs, SIAM Journal on Optimization 8(4): 973-988. Zbl0912.90219
  16. Kantorovich, L. (2006a). On a problem of Monge, Journal of Mathematical Sciences 133(4): 225-226. Zbl1080.49508
  17. Kantorovich, L. (2006b). On the translocation of masses, Journal of Mathematical Sciences 133(4): 1381-1382. Zbl1080.49507
  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. Zbl1305.90304
  19. Levin, V. (2006). Optimality conditions and exact solutions to the two-dimensional Monge-Kantorovich problem, Journal of Mathematical Sciences 133(4): 1456-1463. Zbl1099.49028
  20. Martí, R., Laguna, M. and Glover, F. (2006). Principles of scatter search, European Journal of Operational Research 169(2): 359-372. Zbl1079.90178
  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. Zbl0744.60004
  24. Rachev, S. and Rüschendorf, L. (1998). Mass Transportation Problems, Vol. I, Springer, New York, NY. Zbl0990.60500

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.