La Programación Por Restricciones
Lenguaje de Modelización
Formalismo CSP
Un Problema de Satisfacción de Restricciones (CSP) se define por un conjunto de variables, cada una dotada de un dominio de valores, y un conjunto de restricciones que definen las combinaciones de valores autorizadas. Resolver un CSP equivale a asignar a cada variable un valor de su dominio, de modo que las restricciones del modelo sean verificadas. Se habla de Programación Por Restricciones (PPC), porque el problema a resolver se describe de manera declarativa por el conjunto de sus restricciones.
De la satisfacción a la optimización bajo restricciones
Cuando el problema posee, además de las restricciones a satisfacer, una o varias funciones a optimizar, se habla entonces de Problema de Optimización bajo Restricciones (COP). Tales criterios pueden emerger de consideraciones económicas (minimizar el coste de la solución), organizativas (suavizar al máximo la carga de trabajo), o incluso técnicas (maximización del respeto de las restricciones cuando no pueden ser todas satisfechas. Se habla entonces de restricciones flexibles.). Si la literatura científica académica se focaliza a menudo en los problemas de satisfacción de restricciones, la casi totalidad de los problemas industriales tratados por Cosling son problemas de optimización multi-objetivo.
Un enfoque declarativo
La PPC es un paradigma de programación denominado declarativo: en lugar de indicar un procedimiento a seguir para obtener una solución, nos contentamos con especificar las propiedades que caracterizan la solución buscada. Esta separación neta entre los aspectos funcionales y los aspectos técnicos va mucho más allá de la programación informática, se trata de otra manera de pensar que facilita enormemente los intercambios con el negocio durante proyectos industriales. Saber más.
"Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it."
[Eugene C. Freuder, Constraints, 1997]
Resolución del modelo
Mecanismos del solucionador
Una vez efectuado el trabajo de modelización, un modelo de Programación Por Restricciones puede ser resuelto por un solucionador de restricciones genérico, tal como Choco Solver. Los algoritmos de filtrado de restricciones van a eliminar los valores inconsistentes por deducciones lógicas mientras que las heurísticas de búsqueda del solucionador van a explorar de manera inteligente el espacio de búsqueda residual, mediante un conjunto de hipótesis refutables. La resolución de un CSP por un solucionador de restricciones reposa por tanto en la alternancia de estos dos conceptos fundamentales, filtrado y exploración, hasta obtener una solución factible o probar que no existe ninguna.
Optimización de los Tiempos de cálculo
Los problemas industriales siendo a menudo a la vez muy complejos y de gran tamaño, el tiempo de cálculo puede convertirse rápidamente en un desafío importante. Para aumentar las prestaciones del solucionador, a veces es juicioso enriquecer el modelo con componentes avanzados, como una restricción global, una heurística de búsqueda integrando un saber hacer empresarial o incluso búsqueda local. Esta actividad requiriendo una experiencia en Programación Por Restricciones y un buen conocimiento del solucionador, ¡recurra a nuestros expertos para resolver eficazmente sus problemas complejos!
