Programación de restricciones
La programación de restricciones (PPC) permite resolver problemas de tipo Satisfacción de restricciones (CSP). Un CSP es un problema de modelado en forma de un conjunto de restricciones impuestas a las variables, cada una de estas variables tomando sus valores en un dominio definido.
Un CSP se define por un triplete (X, D, C, R) tal que:
- X = {X1, X2,…, Xno} el conjunto de variables del problema;
- D una función que se asocia con cada variable XI su dominio (conjunto de valores posibles) D (XI);
- C = C1, VS2,…, VSk} el conjunto de restricciones.
Solución de programación de restricciones
Resolver un CSP consiste en asignar valores a las variables, de manera que se satisfagan todas las restricciones. Para ello, necesitamos un vocabulario preciso:
- Una asignación es una instancia de ciertas variables por valores de sus respectivos dominios. Denotaremos por A = {(X1, V1),…} Asignación que instancia la variable X1 por el valor V1, etc;
- Se dice que una asignación es total si instancia todas las variables del problema; de lo contrario, se dice que es parcial;
- Una asignación A viola una restricción Ck si todas las variables de Ck se instancian en A y si la relación definida por Ck no es verificado por la asignación:
- Una asignación total o parcial es consistente si no viola ninguna restricción; de lo contrario, se dice que es inconsistente;
- Una solución CSP es una asignación total consistente.
En la programación de restricciones, cuando un CSP no tiene una solución, se dice que está demasiado restringido. En este caso, podemos encontrar la asignación total que viola la menor cantidad de restricciones posibles. Luego hablamos de max-CSP.
Otra posibilidad en la programación por restricciones es asignar un peso a cada restricción, luego se busca minimizar el peso de las restricciones violadas. Hablamos entonces de VCSP (valorado). Un max-CSP es un VCSP donde todas las restricciones tienen el mismo peso.
Cuando un CSP admite varias soluciones diferentes, se dice que está sub-restringido. Si las soluciones no son todas equivalentes, entonces es posible establecer preferencias entre las soluciones. Agregamos una función que asocia un valor numérico a cada solución, representando la calidad de esta solución. El objetivo es maximizar esta función objetivo. Hablamos entonces de CSOP (satisfacción de restricciones mejoramiento problema).
Ejemplo de programación de restricciones: problema de n-reinas
Un constructor tiene un terreno con 16 parcelas (4 filas y 4 columnas) que forman un tablero de ajedrez. Quiere deshacerse de las turbinas eólicas de tal manera que no se activen. Se activan dos aerogeneradores si están en la misma fila, la misma columna o la misma diagonal.
Programación de restricciones 1
Las variables son las posiciones de las filas y columnas de las turbinas eólicas en el tablero de ajedrez. Asociamos a cada aerogenerador i dos variables LI y CI correspondientes respectivamente a la fila y la columna sobre la que colocar el aerogenerador. Tenemos el siguiente modelado de programación de restricciones:
- Variables:
- X = {L1, LOS2, LOS3, LOS4, VS1, VS2, VS3, VS4}
- Áreas:
- D (L1) = D (L2) = D (L3) = D (L4)={1,2,3,4}
- D (C1) = D (C2) = D (C3) = D (C4)={1,2,3,4}
- Restricciones:
- VSlig = allDiff ({L1, LOS2, LOS3, LOS4}) para tener valores LI todos diferentes entre sí
- VScollar = allDiff ({C1, VS2, VS3, VS4}) para tener valores CI todos diferentes entre sí
- VSdm= {CI+ LI ! = Cj+ Lj / para todo i y j en {1, 2, 3, 4} e i! = j}
- VSdd= {CI-LOSI ! = Cj-LOSj / para todo i y j en {1, 2, 3, 4} e i! = j}
- Es la unión de estos juntos.
Esta modelización es ingenua ya que uno considera todas las limitaciones sin buscar su significado.
Programación de restricciones 2
Es fácil notar que habrá al menos una turbina eólica por columna del tablero de ajedrez (o fila, etc.). La programación por restricciones entonces consiste en determinar en qué fila se ubica el aerogenerador en la columna i, la variable se anotará XI :
- Variables:
- X = {X1, X2, X3, X4}
- Áreas:
- D (X1) = D (X2) = D (X3) = D (X4)={1,2,3,4}
- Restricciones:
- VSlig = allDiff ({X1, X2, X3, X4}) para tener valores XI todos diferentes entre sí
- VSdm= {XI+ yo! = Xj+ j / para todo i y j en {1, 2, 3, 4} e i! = j}
- VSdd= {XI-i! = Xj-j / para todo i y j en {1, 2, 3, 4} e i! = j}
- Es la unión de estos juntos.
Discusión
Hay muchas otras formas de modelar el problema. En este caso, ¿cuál es el mejor modelado? Para eso, existen tres criterios que permiten evaluar la relevancia del modelado: ¿modela mejor el problema? ¿Fue trivial el modelado? ¿El modelado permite resolver el problema de forma eficaz?
Resolución de un CSP
La resolución de un CSP es un problema Np-Complete en el caso general. El mecanismo de resolución consiste en repetir los dos pasos siguientes:
- reducción de problemas mediante filtrado;
- navegando por el árbol de búsqueda.
Estas dos etapas hacen uso de nociones como la consistencia de arcos o la propagación de restricciones que no desarrollaremos en este curso. Hay muchos solucionadores de un CSP como, por ejemplo, la biblioteca de herramientas OR de Google.
ES 
FR 
EN