Matheurística

Nombramos Matheurísticas a aquellos algoritmos de optimización derivados de la interoperación de metaheurísticas y técnicas de programación matemática (PM). Una de sus características esenciales es la explotación, en alguna parte del algoritmo, de características derivadas del modelo matemático del problema que resolver, de ahí el uso de la definición “metaheurísticas basadas en modelos”, presente en eventos y sitios web relacionados con las matheurísticas.

Este campo pretende explotar las ventajas que brindan los modelos y técnicas de la PM en el desarrollo de plataformas (meta)heurísticas, combinándose con la robustez y efectividad de estas últimas. Dentro de la comunidad de investigadores afines, a muchos ha atraído el tema, produciéndose así la publicación de ediciones especiales de libros y revistas dedicados a este tópico. [1] [2]

Desarrollo y Perspectivas

Urge advertir que el uso de la Programación Matemática para resolver problemas de optimización de manera heurística es mucho más antiguo y más extendido que el de las matheurísticas. Aunque la idea de diseñar métodos de PM específicamente para soluciones heurísticas tiene rasgos inovadores que la diferencian de la práctica común de convertir métodos exactos de la PM en heurísticas cuando no hay suficiente disponibilidad de recursos computacionales. Por el contrario, en el caso de las metaheurísticas, la aplicación de modelos y técnicas de la PM es una tendencia novedosa.

Ciertos enfoques que se sirven de una combinación de PM con metaheurísticas están apareciendo de forma regular en la literatura especilizada. Tales combinaciones pueden estar orientadas hacia dos direcciones: una de ellas, que es además la más recorrida hasta el momento, es el empleo de la PM para mejorar o diseñar metaheurísticas, la otra consiste en el uso de estas últimas para mejorar las técnicas ya conocidas de la PM.

Aunque vincula dos de los campos más arraigados de la optimización matemática, la matheurística apenas está en su infancia. Se hace por tanto difícil precisar en que dirección se concentrará el futuro desarrollo de este campo. Algunas de las principales líneas de investigación desarrolladas hasta el momento han sido:

• La utilización de técnicas de la PM para mejorar la búsqueda local. Por ejemplo la utilización de técnicas de poda de la Programación Entera Mixta (PEM) para la exploración de grandes vecindades alrededor de soluciones prometedoras.

• La hibridación de (meta)heurísticas y técnicas exactas de la PM. Por ejemplo, la utilización de modelos de la PM para la solución de subproblemas dentro de una metaheurístca determinada o para mejorar ciertos operadores heurísticos.

• La utilización de técnicas ‘clásicas’ de la PM como la relajación Lagrangeana o la descomposición de Bender para guíar y modificar las operaciones de heurísticas subordinadas.

• La aplicación de modelos matemáticos como fundamento para el diseño de nuevas metaheurísticas.

Véase también

Bibliografía

• Hybridizing Metaheuristics and Mathematical Programming. Series: Annals of Information Systems , Vol. 10 Maniezzo, Vittorio; Stützle, Thomas; Voß, Stefan (Eds.) 2009. [3]

• Special Issue on Mathematical Contributions to Metaheuristics. Guest Editors: Vittorio Maniezzo, Stefan Voß, and Pierre Hansen [4]

• Marco A. Boschetti, V. Maniezzo, M. Roffilli and Antonio Bolufé Röhler. Matheuristics: Optimization, Simulation and Control. HM 2009, LNCS 5818, pp. 171–177, 2009. Springer-Verlag Berlin Heidelberg 2009

• I. Dimitrescu and T. Stutzle. Usages of exact algoritms to enhance stochastic local search algorithm. In V. Maniezzo, T. Stutzle, and S. Voss, editors, Matheuristics: Hibridizing metaheuristics and mathematical programming, OR/CS Interfaces Series. Springer, 2009.

• M. Fischetti and A. Lodi. Local branching. Mathematical Programming B, 98:23-47, 2003.

• E. Danna, E. Rothberg, C. Le Pape. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming 102, 71-90, 2005.

• M. Yagiura and T. Ibaraki. The use of dynamic programming in genetic algorithms for permutation problems. European Journal of Operational Research, 92:387-401, 1996.

• M. Fischetti, F. Glover, and A. Lodi. The feasibility pump. Mathematical Programming, 104(1):91–104, 2005.

• M. Boschetti and V. Maniezzo. Benders decomposition, lagrangean relaxation and metaheuristic design. Journal of Heuristics, pages 1-30, 2007. [5]

• E. Bartolini and A. Mingozzi. Algorithms for the non-bifurcated network design problem. Journal of Heuristics, 15(3):259-281, 2009. [6]

Enlaces externos

• Matheuristics 2006 1st Workshop on Mathematical Contributions to Metaheuristics.
• Matheuristics 2008 2nd International Workshop on Model-Based Metaheuristics
• Matheuristics 2010 3rd International Workshop on Model-Based Metaheuristics