Programación con restricciones dinámica

Resumen

Este trabajo presenta algoritmos de resolución de Problemas de Satisfacción de Restricciones, capaces de medir el desempeño de su proceso a través de indicadores relevantes, posibilitando su auto-ajuste. Las posibilidades de adaptación tienen relación con cambiar la Estrategia de Enumeración en uso al detectarse un mal rendimiento. El propósito es encontrar soluciones rápidamente para diferentes tipos de problemas, solucionando una de las limitantes en torno a las Estrategias de Enumeración: “para un problema dado, se tiene una estrategia particular que funciona bien, pero limitada en la resolución eficiente de otros problemas”.
La propuesta descrita se inspira en enfoques adaptativos existentes, pero que han sido diseñados con otra orientación, como el caso de la Satisfacción de Restricciones Adaptativas, donde dada una secuencia de algoritmos a utilizar, los malos son detectados y reemplazados por el próximo candidato. Sin embargo, en este trabajo no se pretende cambiar un algoritmo completo, sino para un mismo algoritmo de resolución modificar la estrategia que lo guía en base a la observación del conjunto de indicadores, obtenidos del análisis del mismo proceso de búsqueda que está desempeñando.

This paper presents algorithms for solving Constraint Satisfaction Problems (CSPs) capable of measure the performance of their process through relevant indicators to enable adaptations (self-adjust). The adaptation options are related to the change of Enumeration Strategy, used when bad performance is detected. Done in this way, to find quickly solutions to different problems, solving one of the limitations on the Enumeration Strategy: “for a given problem, there is a particular strategy that works very well, but limited in the efficient resolution of other problems.”
The proposal outlined is based on existing approaches, that have been designed with other orientation, such as Adaptive Constraint Satisfaction (ACS), where given a sequence of algorithms to use, bad ones are detected and replaced by the next candidate. However, this paper is not intended to change a complete algorithm, but for the same algorithm, modify the strategy that guides it based on the observation of the set of indicators obtained from the analysis of the search process that is playing.