Metalgoritmo de optimización combinatoria mediante la exploración de grafos.

Abstract

Actualmente, aunque existen procedimientos específicos para resolver de forma óptima algunos problemas concretos de optimización combinatoria, la mayoría se deben solucionar con técnicas generales de exploración del espacio de soluciones, y más concretamente mediante procedimientos de exploración enumerativos en árboles y grafos de búsqueda.<br/><br/>Se analizan los procedimientos de este tipo expuestos en la literatura, tanto en el área de la investigación operativa como en el de la inteligencia artificial, se realiza un estudio crítico que muestra las controvertidas y confusas relaciones que existen entre estas estrategias de resolución, para proponer, en último término, la necesidad de una formalización general que englobe a todas ellas.<br/><br/>Concretamente, los objetivos y aportaciones de esta tesis son los siguientes:<br/><br/>- Recopilación, análisis y crítica de diferentes procedimientos, estrategias de resolución y formulaciones generales de dichas técnicas expuestas en la literatura.<br/><br/>- Propuesta y formalización de branch and win: un metalgoritmo de exploración de grafos que engloba a los diversos procedimientos de búsqueda (branch and bound, programación dinámica, A*, etc.), y que, además, incorpora la posibilidad de utilizar las nuevas herramientas que se están desarrollando en el campo de la inteligencia artificial (técnicas de consistencia y de propagación local de restricciones).<br/><br/>- Diseño y proposición de nuevos procedimientos híbridos a partir de branch and win, resultado de la combinación de los ya existentes y de la incorporación de diversas ideas de carácter general.<br/><br/>Las hipótesis de trabajo adoptadas presentan las siguientes implicaciones. Por un lado no se resuelven problemas combinatorios con datos aleatorios, ni aquéllos que deben resolverse dentro de un entorno dinámico. Y, por otro, tampoco se formalizan los procedimientos bidireccionales ni los basados en representaciones AND/OR (cabe destacar, sin embargo, que en este caso no se restringe de ninguna manera los problemas combinatorios que es posible resolver).<br/><br/>La originalidad de la tesis reside en el diseño de branch and win, cuyas características principales son: es general, integrador, realista (incorpora aspectos importantes en la resolución de problemas industriales), utiliza terminología clara, dinámico (en función de la evolución de la arborescencia y/o del entorno) y derivador de otros procedimientos.<br/><br/>Se ha realizado una implementación informática del metalgoritmo propuesto para dos conocidos problemas de optimización combinatoria (flow shop y cubrimiento), que ha permitido validar la generalidad de branch and win, así como obtener una serie de recomendaciones sobre la conveniencia de probar la adecuación de un conjunto de estrategias: invertir tiempo en la búsqueda de una solución inicial de calidad, utilizar funciones de evaluación y selección dinámicas, utilizar "en cascada" diversos procedimientos del mismo tipo, uso de procedimientos de reducción y de resolución heurísticos en los vértices intermedios de la arborescencia, incorporación de procedimientos de exploración de entornos al obtener una nueva solución factible, etc.<br/><br/>En cuanto a las posibles extensiones y derivaciones de esta tesis, existe un gran campo de investigación abierto en la dirección de probar, para diferentes problemas de optimización combinatoria, nuevos procedimientos híbridos, que se pueden obtener al combinar y utilizar de diversas maneras los elementos que forman branch and win. Esta investigación se concretaría en ensayar el impacto de los diferentes elementos que forman el metalgoritmo propuesto, con el objetivo de encontrar reglas generales para la resolución efectiva de diferentes problemas de optimización combinatoria o de familias de problemas de características similares.