Matheurística

Nomenem Matheurística a aquells algoritmes d'optimisació derivats de la interoperación de metaheurísticas i tècniques de programació matemàtica (PM). Una de les seues característiques essencials és l'explotació, en alguna part de l'algoritme, de característiques derivades del model matemàtic del problema que resoldre, d'ahí l'us de la definició “metaheurísticas basades en models”, present en events i llocs web relacionats en les matheurísticas.

Este camp pretén explotar les ventages que brinden els models i tècniques de la PM en el desenroll de plataformes (meta)heurístiques, combinant-se en la robustea i efectivitat d'estes últimes. Dins de la comunitat d'investigadors afins, a molts ha atret el tema, produint-se aixina la publicació d'edicions especials de llibres i revistes dedicats a este tòpic. [1] ^{[enllaç trencat]}

Desenroll i perspectives

Urge advertir que l'us de la Programació Matemàtica per a resoldre problemes d'optimisació de manera heurística és molt més antic i més estés que el de les matheurísticas. Encara que l'idea de dissenyar métodos de PM específicament per a solucions heurístiques té traces innovadores que la diferencien de la pràctica comuna de convertir métodos exactes de la PM en heurístiques quan no hi ha suficient disponibilitat de recursos computacionals. Pel contrari, en el cas de les metaheurísticas, l'aplicació de models i tècniques de la PM és una tendència nova.

Certs enfocaments que se servixen d'una combinació de PM en metaheurísticas estan apareixent de forma regular en la lliteratura especialisada. Tals combinacions poden estar orientades cap a dos direccions: una d'elles, que és ademés la més recorreguda fins al moment, és l'ocupació de la PM per a millorar o dissenyar metaheurísticas, l'atra consistix en l'us d'estes últimes per a millorar les tècniques ya conegudes de la PM.

Encara que vincula dos dels camps més arraïlats de l'optimisació matemàtica, la matheurística a penes està en la seua infància. Es fa per tant difícil precisar que direcció es concentrarà el futur desenroll d'este camp. Algunes de les principals llínees d'investigació desenrollades fins al moment han segut:

• L'utilisació de tècniques de la PM per a millorar la busca local. Per eixemple l'utilisació de tècniques de poda de la Programació Sancera Mixta (PEM) per a l'exploració de grans veïnats al voltant de solucions prometedores.

• L'hibridació de (meta)heurístiques i tècniques exactes de la PM. Per eixemple, l'utilisació de models de la PM per a la solució de subproblemas dins d'una metaheurístca determinada o per a millorar certs operadors heurístics.

• L'utilisació de tècniques ‘clàssiques’ de la PM com la relaixació Lagrangeana o la descomposició de Bender per a guiar i modificar les operacions d'heurístiques subordinades.

• L'aplicació de models matemàtics com a fonament per al disseny de noves metaheurísticas.

Vore també

• Metaheurística
• Heurística
• Programació Matemàtica
• Investigació d'operacions
• Model matemàtic
• Espai de busca
• Optimisació multiobjetivo

Bibliografia

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

• Special Issue on Mathematical Contributions to Metaheuristics. Guest Editors: Vittorio Maniezzo, Stefan Voß, and Pierre Hansen ^{[enllaç trencat]}

• 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 Interfaços Series. Springer, 2009.

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

• E. Danna, E. Rothberg, C. Li 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. ^{[enllaç trencat]}

• E. Bartolini and A. Mingozzi. Algorithms for the senar-bifurcated network design problem. Journal of Heuristics, 15(3):259-281, 2009. ^{[enllaç trencat]}