Matheurística

Anomenem matheurístiqus a aquells algorismes d'optimització derivats de la interoperació de metaheurístiques i tècniques de programació matemàtica (PM). Una de les seves característiques essencials és l'explotació, en alguna part de l'algorisme, de característiques derivades del model matemàtic del problema a resoldre, d'aquí l'ús de la definició "metaheurístiques basades en models", present en esdeveniments i llocs web relacionats amb les matheurísticas.

Aquest camp pretén explotar els avantatges que ofereixen els models i tècniques de la PM en el desenvolupament de plataformes (meta) heurístiques, combinant-se amb la robustesa i efectivitat d'aquestes últimes. Dins la comunitat d'investigadors afins, a molts ha atret el tema, produint així la publicació d'edicions especials de llibres i revistes dedicats a aquest tòpic.

Desenvolupament i perspectives

És urgent advertir que l'ús de la Programació Matemàtica per a resoldre problemes d'optimització de manera heurística és molt més antic i més estès que el de les matheurísticas. Encara que la idea de dissenyar mètodes de PM específicament per a solucions heurístiques té trets innovadors que la diferencien de la pràctica comuna de convertir mètodes exactes de la PM en heurístiques quan no hi ha prou disponibilitat de recursos computacionals. Per contra, en el cas de les metaheurístiques, l'aplicació de models i tècniques de la PM és una tendència nova.

Certs enfocaments que se serveixen d'una combinació de PM amb metaheurístiques estan apareixent de forma regular en la literatura especialitzats. Aquestes combinacions poden estar orientades cap a dues direccions: una, que és més la més recorreguda fins al moment, és l'ús de la PM per millorar o dissenyar metaheurístiques, l'altra consisteix en l'ús d'aquestes últimes per a millorar les tècniques ja conegudes de la PM.

Encara que vincula dos dels camps més arrelats de l'optimització matemàtica, la matheurística tot just està en la seva infància. Es fa per tant difícil precisar en quina direcció es concentrarà el futur desenvolupament d'aquest camp. Algunes de les principals línies d'investigació desenvolupades fins ara han estat:

• La utilització de tècniques de la PM per millorar la cerca local. Per exemple la utilització de tècniques de poda de la Programació Sencera Mixta (PEM) per a l'exploració de grans veïnatges voltant de solucions prometedores.
• La hibridació de (meta) heurístiques i tècniques exactes de la PM. Per exemple, la utilització de models de la PM per a la solució de subproblemes dins d'una metaheurístca determinada o per millorar certs operadors heurístics.
• La utilització de tècniques 'clàssiques' de la PM com la relaxació Lagrangeana o la descomposició de Benders per guiar i modificar les operacions d'heurístiques subordinades.
• L'aplicació de models matemàtics com a fonament per al disseny de noves metaheurístiques.

Vegeu també

• Metaheurística
• Heurística
• Programació matemàtica
• Investigació d'operacions
• Model matemàtic

Bibliografia

• Hybridizing Metaheuristics and Mathematical Programming. Sèries: Annals of Information Systems, Vol 10 Maniezzo, Vittorio; Stützle, Thomas; Voß, Stefan (Eds.) 2009. «Enllaç».
• Special Issue on Mathematical Contributions to Metaheuristics. Guest Editors: Vittorio Maniezzo, Stefan Voß, and Pierre Hansen «www.springerlink.com».
• Marc 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. Usage of exact algoritms to enhancer stochastic local search algorithm. In V. Maniezzo, T. Stutzle, and S. Voss, editors, Matheuristics: Hibridizing metaheuristics and Mathematical programming , OR/CS Interfícies 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 solucions. 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, Lagrange relaxation and metaheuristic design. Journal of Heuristics , pages 1–30, 2007. «Enllaç».
• E. Bartolini and A. Mingozzi. Algorithms for the non-bifurcated network design problem. Journal of Heuristics , 15 (3) :259-281, 2009. «Enllaç».