19.30 horas.

La metodología CSP (“Constraint Satisfaction Problems”) permite abordar una amplia gama de problemas en los que la solución puede especificarse mediante la satisfacción de un conjunto de restricciones (lógicas, algebraicas, etc.). La implementación de algoritmos capaces de resolver problemas CSP, en forma eficiente, ha dado lugar a la Programación con Restricciones (CP o “Constraint Programming”). Este enfoque involucra tanto la formulación del problema bajo el formato CSP, como la resolución del mismo mediante un conjunto de “solvers” apropiados.

Actualmente existen ambientes comerciales (ILOG, ECLiPSe) para el abordaje de problemas combinatorios que pueden ser resueltos en forma eficiente mediante el enfoque CP. Dichos ambientes poseen la ventaja de incluir bloques constructores predefinidos a nivel de variables, restricciones y algoritmos de búsqueda. Asimismo, permiten a los usuarios establecer estrategias de búsqueda específicas (generalmente dependientes del dominio de trabajo) e incorporarlas de manera sencilla al proceso de resolución. El contar con herramientas de alto nivel, permite tratar reales problemas de gran dificultad (“scheduling”, “timetabling”, asignación, configuración, ruteo de vehículos, etc.) con relativa simpleza, por lo que este tipo de ambientes se ha popularizado.

En esta charla se realiza una presentación de las metodologías CSP y CP, se introducen los algoritmos clásicos (Backtracking, Backjumping, Forward Checking, MAC – Maintaining Arc Consistency, etc.) de generación de soluciones y se describen algunos “bloques constructores” típicos. A continuación, se presentan algunas aplicaciones del dominio de “scheduling” y problemas relacionados. Finalmente, se puntualizan las principales fortalezas y debilidades de este enfoque.